[백준 12852 파이썬] 1로 만들기 2 (실버 1, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : △

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
mem = [0]*(N+1) # 연산 횟수 메모이제이션
path = ["" for _ in range(N+1)] # 최단 경로
path[1] = "1"

for idx in range(2, N+1):
    mem[idx] = mem[idx-1] + 1
    prev = idx-1
    if idx % 3 == 0 and mem[idx//3]+1 < mem[idx]:
        mem[idx] = mem[idx//3] + 1
        prev = idx // 3
    if idx % 2 == 0 and mem[idx//2]+1 < mem[idx]:
        mem[idx] = mem[idx//2] + 1
        prev = idx // 2
    path[idx] = str(idx) + " " + path[prev]

print(mem[N])
print(path[N])

풀이 요약

1. DP 바텀업 방식으로 최소 연산 횟수를 구하되, 그 과정에서 최단 경로를 저장하여 경로도 같이 출력해줘야하는 문제이다.

2. 먼저 전체 문제를 부분 문제에 관한 점화식으로 세워보자.

   count(N) = min(count(N//3), count(N//2), count(N-1)) + 1로 정의할 수 있다.

   count(1) = 0이므로 초기화해주고, 2부터 N까지 순회하면서 메모이제이션 리스트를 활용하여 바텀업 방식으로 쭉 구해나가면 된다.

3. 이 때, prev 변수에 실제로 갱신에 사용된 이전의 수의 path index를 저장해준다.

   그 후, -1, x2, x3 조건문을 모두 거친 후 prev에는 최종적으로 갱신에 사용된 부분 문제 숫자가 담겨있으므로, path[prev]와 현재 숫자를 합하여 path[idx]를 갱신해준다.

배운 점, 어려웠던 점

• 덱으로 풀었다가 TLE가 났다. 이 전의 1로 만들기 문제를 풀었던 풀이를 참고해서 단순 for 순회로 푸는 방법을 적용하고 통과했다. DP를 오랜만에 풀어서 그런가.. 적합한 풀이가 바로 바로 안떠오르는 것 같다.