[이코테] 8-2 1로 만들기(DP)

정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

---

난이도 중하 | 풀이시간 20분 | 시간제한 1초 | 메모리제한 128MB

 

문제

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.1)  X가 5로 나누어 떨어지면 5로 나눈다.2)  X가 3로 나누어 떨어지면 3로 나눈다.
3)  X가 2로 나누어 떨어지면 2로 나눈다.4) X에서 1을 뺀다.

 

정수 X가 주어졌을 때 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소 값을 출력하시오. 

 

입력 조건
첫째 줄에는 정수 X가 주어진다.(1<=X<=30.000)

 

출력 조건
첫째 줄에 연산을 하는 회숫의 최소값을 출력한다.

 

코드 구현

import sys

X=int(sys.stdin.readline().rstrip())

d=[0]*30001 ##  X가 30000까지이므로

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)
    if i%3==0:
        d[i]=min(d[i],d[i//3]+1)
    if i%5==0:
        d[i]=min(d[i],d[i//5]+1)

print(d[X])

해당 문제의 점화식은 아래와 같다. 점화식 끝에 1을 더해주는 이유는 함수의 호출횟수를 구하기 위해서이다.