백준 12852 [1로 만들기 2]

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

12852번: 1로 만들기 2

# 백준 12852
n = int(input())
dp = [[] for _ in range(n+1)]

for i in range(1, n+1):
    if i % 6 == 0:
        if len(dp[i//3]) <= len(dp[i//2]):
            dp[i] = dp[i//3]+[i]
        else:
            dp[i] = dp[i//2]+[i]
    elif i % 3 == 0:
        if len(dp[i//3]) <= len(dp[i-1]):
            dp[i] = dp[i//3]+[i]
        else:
            dp[i] = dp[i-1]+[i]
    elif i % 2 == 0:
        if len(dp[i//2]) <= len(dp[i-1]):
            dp[i] = dp[i//2]+[i]
        else:
            dp[i] = dp[i-1]+[i]
    else:
        dp[i] = dp[i-1]+[i]

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

처음에는 그리디로 접근하였는데, 잘 풀리지 않아 dp로 바꿔서 해결하였다.