정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 피보나치 수열 문제를 도식화했던 것처럼 문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다. 문제에서 요구하는 내용을 점화식으로 표현해보면 아래와 같다.
a(i) = min(a(i-1), a(i/2), a(i/3), a(i/5)) + 1
점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다. 실제 코드로 구현할 때는 1을 빼는 연산을 제외하고는 해당 수로 나누어 떨어질 때에 한해서만 점화식을 적용할 수 있다. 더불어 두 수 중에서 단순히 더 작은 수를 구하고자 할 때는 파이썬에서의 min() 함수를 이용하면 간단하다.
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
for i in range(2, x+1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i%2 == 0:
d[i] = min(d[i], d[i//2]+1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i%3 == 0:
d[i] = min(d[i], d[i//3]+1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i%5 == 0:
d[i] = min(d[i], d[i//5]+1)
print(d[x])