[백준 파이썬] 12852번 1로 만들기 2

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

12852번: 1로 만들기 2

 

<풀이>

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0, []] for _ in range(n+1)]

# dp[i][0] i로 갈 수 있는 계산횟수
# dp[i][1] i로 가는동안 지나간 경로

dp[1][0] = 0
dp[1][1] = [1]

for i in range(2, n+1):
    # +1
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]

    # %3
    if i % 3 == 0 and dp[i//3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]

    # %2
    if i % 2 == 0 and dp[i//2][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]

print(dp[n][0])
print(*dp[n][1][::-1])

 

dp로 풀어야되는데 dp가 어렵네요...

나누어떨어지고 계산횟수가 적을 경우에만 지나온 경로를 바꿔줍니다.