[이코테] 다이나믹 프로그래밍 - 1로 만들기

1/4 Pr. 1로 만들기

난이도 🌕🌗🌑 | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB

정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

ⓐ X가 5로 나누어떨어지면, 5로 나눈다.

ⓑ X가 3으로 나누어 떨어지면, 3으로 나눈다.

ⓒ X가 2로 나누어 떨어지면, 2로 나눈다.

ⓓ X에서 1을 뺀다.

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

예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

1. 26 - 1 = 25 (ⓓ)
2. 25 / 5 = 5 (ⓐ)
3. 5 / 5 = 1 (ⓐ)

입력 조건

• 첫째 줄에 정수 X이 주어진다. (1 ≤ X ≤ 30,000)

출력 조건

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

입력 예시

26

출력 예시

3

해설

elif로 작성하면 안됨 → 2,3,5의 공배수가 있기 때문에, 순서 지키기
Bottom-up, 문제와 반대로 1을 더하는 것이 아니라 빼는 것으로 구현 하는 걸 생각해보기

i in-logic

i=2) d[2] = d[1] + 1 = 0 + 1 = 1
	i % 2 == 0:
		d[2] = min(d[2], d[1] + 1) = min(1, 1) = 1
i=4) d[4] = d[3] + 1 = 2 + 1 = 3
	i % 2 == 0:
		d[4] = min(d[4], d[2] + 1) = min(2, 2) = 2
i=7) d[7] = d[6] + 1 = 2 + 1 = 3
i=8) d[8] = d[7] + 1 = 3 + 1 = 4
	i % 2 == 0:
		d[8] = min(d[8], d[4] + 1) = min(4, 3) = 3

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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])