[백준] 12852번 문제 (1로 만들기 2) 파이썬(Python) 풀이

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

12852번: 1로 만들기 2

n = int(input())

dp = [i for i in range(n + 1)]
dp[1] = 0
history = [i for i in range(n + 1)]
history[1] = 0

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

    if i % 3 == 0 and dp[i] > dp[i // 3] + 1:
        dp[i] = dp[i // 3] + 1
        history[i] = i // 3
    if i % 2 == 0 and dp[i] > dp[i // 2] + 1:
        dp[i] = dp[i // 2] + 1
        history[i] = i // 2

print(dp[n])
print(n, end=" ")

back_num = n
while history[back_num] != 0:
    print(history[back_num], end=" ")
    back_num = history[back_num]

 

https://honggom.tistory.com/87

[백준] 1463번 문제 (1로 만들기) 파이썬(Python) 풀이

위 링크에서 풀었던 문제와 유사하다.

dp를 통해 연산의 최소값을 구하고, 그와 동시에 history에 숫자를 저장한다.

 

마지막에 dp[n] 을 출력해 연산의 최소값을 출력하고,

history를 n 부터 역으로 숫자를 추적하며 출력한다.