백준 1463 : 1로 만들기(DP)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제 요약>

주어진 정수 X에 대하여 X가 1이 될 때까지, 다음 세 연산을 수행한다.

1. X%3 == 0  --> X = X//3

2. X%2 ==0 --> X = X//2

3. X = X-1

연산을 사용하는 횟수의 최솟값은?

 

문제 해설> 

처음엔 X에서 사용한 3가지 연산을 다 수행하면서 1로 가는 값을 계속 업데이트 해줬더니, 메모리 에러가 났다.

거꾸로, 1에서 세가지 연산을 역으로 수행해가면서 10이 되는 순간을 저장해서 메모리 에러를 해결했다.

재귀를 해줄 땐, setrecursionlimit 을 잊지 말자. 

import sys
sys.setrecursionlimit(10**9)
result = []

def solve(n,N):
    while n < N:
        if 3*n <= N:done[3*n] = min(done[n]+1, done[3*n])
        if 2*n <= N :done[2*n] = min(done[n]+1, done[2*n])
        if n+1 <= N:done[n+1] = min(done[n]+1, done[n+1])
        n+=1
    

if __name__ == '__main__':
    N = int(input())
    cnt = 0
    done = {i:N for i in range(1,N+1)}
    done[1]=0
    solve(1,N)
    print(done[N])

예전에 풀었던 이모티콘 문제와 비슷하다.