[백준] 12852번 1로 만들기 2 ★★★

💡문제접근

• 이전 포스팅에 있었던 [[백준] 1463번 1로 만들기]의 응용 문제다. 이 문제에서는 추가로 연산을 사용하는 과정까지 같이 출력해줘야한다. 그래서 [연산을 사용하는 횟수의 최솟값, 연산 과정] 값을 저장했다.

💡코드(메모리 : 379472KB, 시간 : 2324ms)

import sys
input = sys.stdin.readline

N = int(input().strip())
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][0] > dp[i//3][0] + 1:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]
    if i % 2 == 0 and dp[i][0] > dp[i//2][0] + 1:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]

print(len(dp[N][1])-1)
print(*dp[N][1][::-1])

📌연산을 1로 만드는 DP코드문 이해

for i in range(2, N+1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]

💡소요시간 : 40m