12582_1로 만들기 2

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

12852번: 1로 만들기 2

 

이전에 풀어보았었던 내용이지만 값이 엄청 커졌다.

 

 

dp를 활용해서 푸니까 잘 풀렸다.

 

1부터 시작해서 *2, *4, +1 을 해서 저장된 값보다 길이가 적으면 그 값들을 리스트형태로 전달하게 해주었다.

 

n = int(input())
dp = [ [] for i in range(n+1) ]
dp[1].append(1)

for i in range(1,n+1):

    LEN = len(dp[i])
    if i*3 <= n:
        if len(dp[i*3]) == 0 or LEN <len(dp[i*3]) :
            dp[i*3] =  [i*3] +dp[i]
    if i*2 <= n:
        if len(dp[i*2]) == 0 or LEN <len(dp[i*2]) :
            dp[i*2] = [i*2] +  dp[i]
    if i+1 <= n:
        if len(dp[i+1]) == 0 or LEN <len(dp[i+1]) :
            dp[i+1] = [i+1] + dp[i]

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