[Python][프로그래머스] N으로 표현 / DP (Lv3)

🖇️ 링크 

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

---

🗒️ 파이썬 코드 풀이

def solution(N, number):
    answer = 0 
    dp = [set() for _ in range(9)]
    dp[1].add(N)
    
    if number == N : 
        return 1
    
    for p in range(2,9):
        dp[p].add(int(str(N) * p))
        
        for i in range(1,p):
            for x in dp[i] : 
                for y in dp[p-i]:
                    dp[p].add(x+y)
                    dp[p].add(x-y)
                    dp[p].add(x*y)
                    
                    if y != 0 :
                        dp[p].add(x//y)
            if number in dp[p]: 
                return p
        
    return -1

올바른 문제 풀이

 

1. 문제가 4단 for문을 사용해서 상당히 복잡해 보이지만, 핵심만 알면 생각보다 간단하다. 

 

2. 가장 첫번째의 for문의 변수  p는 현재 구하고자 하는 인덱스이다.

 

3. 그리고 1~p 까지의 범위를 갖는 두번째 for문은 아래와 같은 형식을 만들어주기 위함이다.

• 예를들어 p가 4일때, dp[1]-dp[3] / dp[2]-dp[2] / dp[3]-dp[1] 
• 간단하게 말해 x + y 의 합이 p가 되면 됨 

4. 세번째와 네번째 for 문은 dp[x]와 dp[y] 안에 값들을 결합하기 위한 for문이다.

 

5. 이후, 예외 케이스들을 설정해주면 된다.

• dp[1] 초기값 세팅
• 만약 number가 그냥 N 인 경우
• NN 같은 케이스
• 나누셈 할 때, 0으로 나누는 경우

 

막상 이렇게 답을 설명해보니 간단해 보인다.

근데 실전에서 저 예외 케이스를 생각해내는 것만 해도 상당히 힘들 것이다 ...

 

 

시간 복잡도 O( 5 * N) 

→ 문제에서 N은 1이상 9 이하 

시간 복잡도 계산

1,953,125면 약 2백만인데, 이정도면 시간 초과 문제는 없다.

 

 

 

🗒️ 실패한 풀이 

def solution(N, number):
    answer = 0
    limit = 100
    dp = [-1] * (limit+1)
    dp[N] = 1
    
    for p in range(2,9):
        for q in range(limit):
            if dp[q] != -1: 
                print(q,p)
                lst = [(q*10 +N), q+N, q-N, q*N, q//N]
                for k in lst :
                    if k <= limit and dp[k] == -1 :
                        dp[k] = p

            
    return answer

 

1. 처음의 내 접근 방식이다. 

 

2. 나는 dp를 0 ~ 32000 (number의 최대값)으로 해서 안을 채워가는 방식으로 했다.

 

3. 내 풀이에는 여러 문제가 있다.

• N을 여러번 붙이는 경우
• 0으로 나누는 경우 
• dp[q] != -1로 값이 갱신되지 않는 경우에 if문 절을 실행하는데, 연쇄적으로 갱신이 되는 문제 발생
  • 예를 들어, 딱 5만 갱신되고 끝내야하는데, q가 5가 될 때 전에 갱신되어 10이 됨 (무한 반복)

처음 내가 생각했던 방식

 

 

---

📌  문제 코멘트 

이 문제를 포스팅 하는 이유는 다음과 같다.

• 풀었던 DP 중에 가장 어려웠던 문제 
• set(집합)을 이용해 DP를 처음 해봤음
• N이 고정값이 아니라 범위를 가져 4중 for문으로 해야했고, 이 부분 생각해내지 못함
• 이런 문제 시간 복잡도 계산 방법

문제가 어려웠어도 DP의 핵심은 다 똑같다.

→ 초기값 / 예외 케이스 / 메모리제이션

 

---

📚  문제