다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
26
3
바텀업 방식을 이용하여, 1부터 주어진 숫자까지 연산을 사용하는 횟수의 최솟값을 d 리스트에 저장한다. min() 함수를 사용하여 2나 3이나 5로 나눠질 수 있는 경우에 1을 빼거나 나눴을 때 어떤 방법이 최솟값을 구할 수 있는지 정한다.
X = int(input())
d = [0] * 30001
# 2~X까지 연산을 사용하는 횟수의 최솟값 저장, 바텀업 방법
for i in range(2, X + 1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1
# 현재의 수에서 2로 나누는 경우, 1을 뺐을 경우와 비교
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
# 현재의 수에서 3으로 나누는 경우, 1을 뺐을 경우와 비교
elif i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1)
# 현재의 수에서 5로 나누는 경우, 1을 뺐을 경우와 비교
elif i % 5 == 0:
d[i] = min(d[i], d[i//5] + 1)
print(d[X])