[DP/동적계획법] 백준 12852 1로 만들기 2 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

12852번: 1로 만들기 2

 

 

 

2. 문제 풀이

 1로 만드는 최소 연산 횟수와 방법을 출력하는 문제입니다.

 

2022.02.21 - [Algorithm] - [동적계획법/DP] 백준 1463 1로 만들기 - Python

[동적계획법/DP] 백준 1463 1로 만들기 - Python

 1로 만드는 방법론적 설명은 위 링크에서 보실 수 있습니다. '1로 만들기 2'는 1로 만드는 방법까지 출력해야 합니다. 이를 위해서는 추가적으로 경로를 저장하는 리스트를 만들면 됩니다. 탐색에서 parent 또는 path로 경로를 저장하는 것과 같습니다.

 

 

 

3. 코드

N = int(input())
cache = [0]*(N+1) #메모이제이션
path = [[] for _ in range(N+1)] #연산 저장
path[1] = [1]

for i in range(2, N+1):
    # 1을 뺐을 때
    cache[i] = cache[i-1] + 1
    path[i] = path[i-1] + [i]

    # 2로 나누었을 때
    if i % 2 == 0 and cache[i//2]+1 < cache[i]:
        cache[i] = cache[i//2]+1
        path[i] = path[i//2] + [i]

    # 3으로 나누었을 때
    if i % 3 == 0 and cache[i//3]+1 < cache[i]:
        cache[i] = cache[i//3]+1
        path[i] = path[i//3] + [i]

#출력
print(cache[N])
for i in path[N][::-1]:
    print(i, end=' ')

 별도로 path 2차 리스트를 추가했습니다. cache가 갱신될 때마다, path 리스트끼리 더하며 이전까지의 연산과정을 추가합니다.