[백준 / #12852] 1로 만들기 2 (Python)

문제 설명

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

12852번: 1로 만들기 2

 

 

---

문제풀이

1로 만들기 문제에서 그 경로까지 출력해야 하는 문제!

경로를 어떻게 구할까 고민하다가 배열을 하나 더 만들어서 최솟값을 구할 때 그 인덱스를 저장해 놓으면 옮겨간 경로를 구할 수 있을 것 같아서 구현했다.

별 문제 없이 잘 됐다! 

N = int(input())

dp = [0] * 1000001
pre = [0] * 1000001
for i in range(2, N + 1):
    if i % 3 == 0:
        if i % 2 == 0:
            dp[i] = min(dp[i // 3], dp[i // 2], dp[i - 1]) + 1
            if dp[i // 3] == min(dp[i // 3], dp[i // 2], dp[i - 1]):
                pre[i] = i // 3
            elif dp[i // 2] == min(dp[i // 3], dp[i // 2], dp[i - 1]):
                pre[i] = i // 2
            else:
                pre[i] = i - 1
        else:
            dp[i] = min(dp[i // 3], dp[i - 1]) + 1
            if dp[i // 3] == min(dp[i // 3], dp[i - 1]):
                pre[i] = i // 3
            else:
                pre[i] = i - 1
    elif i % 2 == 0:
        dp[i] = min(dp[i // 2], dp[i - 1]) + 1
        if dp[i // 2] == min(dp[i // 2], dp[i - 1]):
            pre[i] = i // 2
        else:
            pre[i] = i - 1
    else:
        dp[i] = dp[i - 1] + 1
        pre[i] = i - 1

print(dp[N])
while N != 1:
    print(N, end=' ')
    N = pre[N]
print(1)

1