백준 12852 1로 만들기 2 - 파이썬

문제.

풀이.

최솟값과 경로를 담는 dp 배열을 생성해서

연산마다 최솟값과 경로를 배열에 담아준다.

그리고 경로를 뒤집어서 출력하면 된다.

 

 

소스코드.

import sys

input = sys.stdin.readline

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):
    # x -1
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]

    # x // 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]
    
    # x // 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])

for i in dp[n][1][::-1]:
    print(i, end=' ')