[동적계획법] 난이도1.5, 이취코 217p '1로 만들기' (Python)

<문제>

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

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
1. 26-1 = 25
2. 25/5 = 5
3. 5/5 = 1

<입력 조건>

• 첫째 줄에 정수 X가 주어진다. (1<=X<=30,000)

<출력 조건>

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

<문제 풀이>

1. 정수 x부터 1까지 연산되는 수의 개수를 구하는 문제이므로 동적계획법 알고리즘을 사용해야 한다.

2. 정수 x부터 1까지 계산된 결과를 저장하기 위해 초기화

3. 보텀업으로 알고리즘 구성

 

<코드>

x = int(input())

d = [0]*30001

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])

 

<고쳐야 할 점>

• 동적계획법 문제라는 것을 인지하기
• 값을 담을 변수 저장 (입력조건 참고)
• 문제 & 답 이해하고 외우기
• 복습 알고리즘