[Algorithm] Baekjoon/DP/1463/1로 만들기

최근, 강화학습을 공부하면서 DP를 접하게 되었다. MP(markov process), MDP(markov decision process)를 공부하면서 DP를 처음 접하게 되었다.

기억나는 표현은 시간적 요소와 공간적 요소(메모리) 사이의 Trad-off라는 것.

즉, 메모리를 조금? 더 사용해서 관심 문제를 상대적으로 빠르게 해결하는 수단이라는 것이다.

특정 계산의 결과를 저장하여, 그 계산이 다시 일어나지 않도록 조치를 취하는 방식으로 작동한다.

백준1463 문제를 해결함에 있어서 DP를 어떻게 써먹을지 한번 고민해 봅시다.

problem

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

my code

from collections import deque
n = int(input())

buf = deque()
temp = (n, 0)
dct = {}

while temp[0] != 1 :
    if temp[0] % 3 == 0 and temp[0]//3 not in dct:
        buf.append((temp[0]//3, temp[1]+1))
        dct[temp[0]//3] = temp[1]+1
    if temp[0] % 2 == 0 and temp[0]//2 not in dct:
        buf.append((temp[0]//2, temp[1]+1))
        dct[temp[0]//2] = temp[1]+1
    if temp[0]-1 not in dct:
        buf.append((temp[0]-1, temp[1]+1))
        dct[temp[0]-1] = temp[1]+1
    temp = buf.popleft()

print(temp[1])

우선 아이디어 설명부터 하겠다.

1. 시작 숫자에서부터 최대 세 가지 연산이 수행될 수 있다. 
2. 시작 숫자를 하나의 노드로 생각하면 최대 세 개의 자식 노드가 생길 수 있다.
3. 문제의 규칙에 맞게 일종의 트리가 생성된다.
4. level이 가장 낮은, 즉 원점으로부터 가장 가까운, 노드(which got 1)의 level이 정답이다.

위의 아이디어를 구현하기 위해 사용한 것은

1. 트리 탐색 중 level-order 탐색(queue 이용)
2. 딕셔너리 이용(실질적인 dynamic programming)

코드를 보면 이해가 되리라

최근에 푼 타노스의 핑거 스냅 문제도 이와 비슷한데 조금 더 복잡하다.
다음 글은 핑거 스냅