[Python] 이것이 코딩테스트다 with 파이썬 - 1로 만들기 - 다이나믹 프로그래밍 (DP)

해당 문제 및 해설은 "이것이 코딩테스트 다 with 파이썬" 책을 기준으로 요약 및 정리하여 작성하였습니다.

 

이것이 코딩테스트다 with 파이썬 구입처

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

---

 

문제 : 1로 만들기

 

정수 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 (4)
2. 25 / 5 = 5 (1)
3. 5 / 5 = 1 (1)

 

입력 조건

첫째 줄에 X 가 주어진다. ( 1 ≤ X ≤ 30,000 )

 

출력 조건

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

 

입력 예시	출력 예시
26	3

 

문제를 풀기 전에

전 블로그와 동일한 문제이고, 조금만 변형된 문제이다.

백준 1463 번 과 같은 문제이며, 최솟값을 보자마자 DP 로 보고 풀면 되는 문제이다.

 

 

코드

import sys

input = sys.stdin.readline

# 정수 X 를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍 (DP) 진행 (보텀 업)
for i in range(2, x + 1):
	# 현재의 수에서 1을 빼는 경우
    d[x] = d[x - 1] + 1
    
    # 현재의 수가 2로 나누어 떨어지는 경우
    if x % 2 == 0:
    	d[i] = min(d[i], d[i//2] + 1)
    
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if x % 3 == 0:
    	d[i] = min(d[i], d[i//3] + 1)
        
    # 현재의 수가 5로 나누어 떨어지는 경우
    if x % 5 == 0:
    	d[i] = min(d[i], d[i//5] + 1)
 
print(d[x])