[백준`S1] 12852 - 1로 만들기 2 (Python)

문제 설명

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

12852번: 1로 만들기 2

 

---

문제 풀이

1로 만들기와 똑같은 문제인데 여기서는 과정을 출력해야 한다 (경로 추적)

처음에는 i마다 i를 1로 만드는 과정들을 2차원 배열로 저장하고,

이전 단계의 배열을 복사해와서 거기에 append를 통해 모든 i의 과정을 저장하는 방법을 사용하였다

n까지 다 구해지면 n을 1로 만드는 과정이 담긴 배열을 reverse 한 후 len과 함께 출력했는데 시간초과...

아마 배열을 복사하는 과정에서 시간초과가 났던 것 같다

 

시간 초과가 나와서 다른 방법을 생각했다

어디서 왔는지 경로를 추적하는 배열을 하나 더 만들었다

예를 들어 graph[i] = 9라면 i에서 9로 가는 것이 최솟값이라는 뜻이다

 

 

n = int(input())

d = [0 for _ in range(n + 1)]
graph = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
    d[i] = d[i - 1] + 1
    x = i - 1
    if i % 3 == 0 and d[i] > d[i // 3] + 1:
        d[i] = d[i // 3] + 1
        x = i // 3
    if i % 2 == 0 and d[i] > d[i // 2] + 1:
        d[i] = d[i // 2] + 1
        x = i // 2

    graph[i] = x

result = [n]
x = n
while x > 1:
    x = graph[x]
    result.append(x)

print(d[n])
print(*result)