다이나믹 프로그래밍_1로 만들기
문제
note
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
- X가 5로 나누어떨어지면, 5로 나눈다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
정수 X 가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
- 26 - 1 = 25
- 25 / 5 = 5
- 5 / 5 = 1
입력 조건
- 첫째 줄에 정수 X가 주어진다.
(1 <= X <= 30,000)
출력 조건
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
입력 예시
26
출력 예시
3
동빈나 풀이
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
for i in range(2, x + 1):
# 현재의 수에서 1빼는 경우
d[i] = d[i - 1] + 1
# 예를 들어, 현재의 수가 2와 3으로 나누어진다고 가정할 때
# 처음엔 1을 뺀 경우와 2로 나누어지는 경우와 비교하지만 최솟값이 2로 나누어지는 경우라면
# 다음부턴 2로 나누어지는 경우와 3으로 나누어지는 경우 중 최솟값을 비교하게 된다.
# 현재의 수가 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])
d[0]과 d[1]은 각각 0으로 초기화됩니다. d[1]은 이미 1이기 때문에 더 이상의 연산이 필요 없으므로 0입니다. 따라서 2부터 x까지 각 숫자에 대해 최소 연산 횟수를 계산합니다.