[Python] 1로 만들기 2 - 백준 (DP)

해당 글은 백준 12852번 '1로 만들기 2' 문제를 다룬다.

문제

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

12852번: 1로 만들기 2

 

설명

해당 문제는 DP로 간단하게 해결할 수 있는 문제인데, 순서도 같이 출력해주어야 하는 게 새로웠던 것 같다.

이를 위해 dp 리스트를 만들 때, 순서도 같이 저장할 수 있는 빈리스트도 추가하여 선언해주었다.

DP로 최소값을 구하는 부분에 순서도 같이 저장해주는 부분만 추가해주면 된다.

 

코드

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

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

for i in range(2, n+1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    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]
    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(*reversed(dp[n][1]))