[이코테] CH08 다이나믹 프로그래밍 실전문제 2번 1로 만들기

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
X = int(input())
d = [0] * 30001

index = 1
for i in range(2,X+1):
    d[i] = d[i-1] + 1
    if i%2 == 0:
        d[i] = min(d[i],d[i//2] + 1)
    elif i%3 == 0:
        d[i] = min(d[i],d[i//3] + 1)
    elif i%5 == 0:
        d[i] = min(d[i],d[i//5] + 1)
        # 여기서 둘중 비교하는 것은 1을 더해주는 것과 각 수를 곱하는 것중 어떤게 최소 카운트가 되는지

print(d[X])

 

DP(다이나믹 프로그래밍) 의 정의:

메모리 공간을 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 방법

- 탑다운 / 보텀업 2가지 방식 존재

탑다운 : 위에서 아래로 구하는 방식(하향식)

보텀업 : 아래서 위로 구하는 방식(상향식)

 

DP를 사용할 수 있는 조건:

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

대체적으로 DP의 전형적인 형태는 보텀업 방식을 사용한다.

그래서 본인 또한 d[2]부터 시작해서 위로 올라가는 방식을 선택했다.