[백준][Python] 12852 1로만들기 2 : 방문 배열을 가져가는 dp

dp로 적당히 뒤집고 설계하니 풀렸다. -1, 3의 곱, 2의곱중 이동횟수가 작은값에 1더해서 저장 + 배열 저장.

 

N = int(input())

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


dp[1][0] = 0
dp[1][1] = [1]
if N>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 not i%3 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 not i%2 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])