[Python] boj no. 12852 : 1로 만들기 2

Problem

https://www.acmicpc.net/problem/12852

Idea

해당 숫자에 도달하는 세 가지 방법 중 최소 횟수의 방법을 선택한다.

1. +1 연산을 통해 도달하는 경우
2. *2 연산을 통해 도달하는 경우
3. *3 연산을 통해 도달하는 경우

해당 과정을 2부터 N까지 반복하면 N에 도달하는 최소 횟수를 알 수 있다.

이 때, 최소 횟수를 사용한 경로를 확인하기 위해 각 선택 과정에서 해당 값에 도달하기 위한 이전 숫자를 저장한다.

Code

N = int(input())

dp = [0 for _ in range(N+1)]
path = [0 for _ in range(N+1)]

for i in range(2, N+1):
    dp[i] = dp[i-1] + 1
    path[i] = i-1
    
    if i % 2 == 0 and dp[i//2]+1 < dp[i]:
        dp[i] = dp[i//2] + 1
        path[i] = i//2
        
    if i % 3 == 0 and dp[i//3]+1 < dp[i]:
        dp[i] = dp[i//3] + 1
        path[i] = i//3

print(dp[N])
cur = path[N]
print(N, end=' ')      
while cur != 0:
    print(cur, end=' ')
    cur = path[cur]

Comment