[백준 12852번] 1로 만들기 2 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
INF = 10**9

N = int(input())

DP = [INF]*(N+1)
last = {}

dq = deque()
dq.append(1)
DP[1] = 0

while dq:
  n = dq.popleft()
  if n*3<N+1:
    if DP[n*3] > DP[n]+1:
      DP[n*3] = DP[n]+1
      last[n*3] = n
      dq.append(n*3)
  if n*2<N+1:
    if DP[n*2] > DP[n]+1:
      DP[n*2] = DP[n]+1
      last[n*2] = n
      dq.append(n*2)
  if n+1<N+1:
    if DP[n+1] > DP[n]+1:
      DP[n+1] = DP[n]+1
      last[n+1] = n
      dq.append(n+1)

print(DP[N])

while 1:
  print(N,end=" ")
  try:
    N = last[N]
  except:
    print()
    break

가장 기초적인 DP문제인 1로만들기 문제에서 경로만 추가되었다.

last dictionary를 만들어서 DP값이 바뀔때마다 그전 값을 딕셔너리에 저장하고, 마지막에 last 값을 순서대로 출력하는 방식으로 구현하였다.

 

 

오늘의 교훈) 음... 열심히하자