문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

나의 코드 (4점)

from collections import deque

def solution(x, y, n):
    # y부터 x까지 거꾸로 기록해나갈 수 있는 dp table에 1e9를 할당해 둠.
    dp = [1e9 for i in range(y - x + 1)]
    # dp table에서 y에 해당하는 숫자는 0을 할당해 둠
    dp[y - x] = 0
    # deque 라이브러리 킹왕짱
    queue = deque([y])
    
    
    while queue:
        cur = queue.popleft()
    # 비로소 x와 같은 숫자가 나오면 dp table에서 x에 해당하는 값 return
        if cur == x:
            return dp[0]
        # n을 뺐는데 아직 x보다 크거나 같다면
        if cur - n >= x :
        # cur - n번째 숫자에 메모. x를 빼주는 이유는 dp table 에서 숫자 35에 해당하는 값을 25번째 인덱스에 메모해야 하기 때문이다.
                dp[cur - n - x] = min(dp[cur - n - x], dp[cur - x] + 1)
                queue.append(cur -  n)
                
        if cur % 2 == 0 and cur // 2 >= x :
                dp[cur // 2 - x] = min(dp[cur // 2 - x], dp[cur - x] + 1)
                queue.append(cur // 2)
                
        if cur % 3 == 0 and cur // 3 >= x :
                dp[cur // 3 - x] = min(dp[cur // 3 - x], dp[cur - x] + 1)
                queue.append(cur // 3)
                
   # queue가 빌 때까지 x와 같은 숫자가 안 나오면 노답인거임.
    return -1

초딩이 그린 그림 아님 주의

지저분한 초딩 낙서 같지만, 자세히 보면 내가 문제를 풀었던 아이디어가 잘 담겨 있어서 약간의 웃음벨도 있어서 가져왔다. 파이썬으로 풀거면서 아직도 js가 익숙하니 무의식적으로 shift()라고 메모한 게 웃기닼ㅋㅋ 40에 불가사리는 왜 그린거??

아이디어

• x에서 y로 가는 것보다 y에서 x로 갈 때 고려해야 할 경우의 수가 더 적어져서 불필요한 연산이 줄어든다. 2나 3으로 나누어 떨어져야만 연산을 계속하기 때문이다.

  • 예를 들어서 x = 10, y = 40, n = 5일 때,
    x에서 y로 갈 때는 x = 10일 때 15, 20, 30을 고려하고, 그 다음에는 또 각각의 숫자에 3가지 연산을 해주고 y = 40이 나올 때까지 반복이다. 매 단계에서 고려해야 하는 경우의 수가 3배씩 늘어난다.

  • 반면 y = 40에서 시작해서 x로 내려오면 n = 5를 빼면 35가 되고, 35에서는 2와 3으로 나눠 지지 않으므로 다음 번에는 30 하나만 고려하면 된다.

• DP를 떠올렸다. 반복되는 연산을 계속 하는데 다른 숫자의 연산을 하다가 돌아와야 하기 때문에 dp table에서 값을 가져오는 게 최적일 듯 했다. 나에게 관건은 처음으로 큰 수부터 내려오면서 특정 배열의 범위에서 메모이제이션을 구현해보는 것이었다.

• queue를 떠올렸다. 각 단계 별로 숫자마다 3가지 이하의 연산(-n, 2의 배수일 경우 나누기 2, 3의 배수일 경우 나누기 3)을 하게 되는데, 하나의 숫자가 메모될 때마다 다음 단계에서 연산을 또하려면 차례대로 불러와야 하므로 queue를 써서 선입선출(FIFO)로 순차적으로 append하고 빼오는 게 직관적인 듯 했다.

어려웠던 점

list index out of range 오류가 꽤 많이 났다.
거꾸로 내려오는 방식으로 결정했고, x부터 y까지의 숫자들만 담는 list가 필요했는데, dp table에서 원소를 참조할 때마다 인덱스를 잘 지정해줘야 했다.
아직 python list의 원소의 개수를 미리 지정해 놓고 그 안에서만 원소를 컨트롤 할 수 있다는 게 적응이 더 필요할 것 같다.

오랜만에 4점 받으니 뿌듯하구만~~ 그래도 아직 연습이 더 많이 필요하다 후 화이팅!!!