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

📌 이 문제는 해당 책에서 가져왔습니다.

1로 만들기: 문제 설명

문제 설명

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

1. X가 5로 나누어 떨어지면, 5로 나눈다.
2. X가 3으로 나누어 떨어지면, 3으로 나눈다.
3. X가 2로 나누어 떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

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

26 -> 25 -> 5 -> 1

입력 조건

첫째 줄에 정수 X가 주어집니다.

출력 조건

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

입력 예시 및 출력

• 입력 예시:
  26
• 출력 예시:
  3

문제 해결 아이디어

• 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그려보면 다음과 같습니다.
  • 최적 부분 구조와 중복되는 부분 문제를 만족합니다.

앞서 그리디 파트에서 다루었던 1이 될 때까지 문제와는 차이가 있음. 해당 변수가 어떤 값을 가지던 간에 1을 빼는 것보다 나누는 것이 1로 만드는 더 빠른 과정이기 때문에 최적의 값을 찾는 것이 그리디의 방법이었는데요.

현재 문제는 단순히 그리디의 방법으로 해결하기는 어렵습니다.

26의 경우도 1을 뺀 다음에 5로 두 번 나눠서 1을 만드는 방법이 3번 만에 1을 만드는 가장 빠른 방법이었는데요.

각 문제는 작은 문제를 조합해서 해결할 수 있기 때문에 최적 부분 구조를 갖고 있으며, 중복되는 부분 문제를 만족한다고 볼 수 있습니다.

• $a_i=1$ 를 1로 만들기 위한 최소 연산 횟수
• 점화식은 다음과 같음

$a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}+ 1$)

• 단, 1을 빼는 연산을 제외하고는 해당 수로 나누어질 때 한해 점화식을 적용할 수 있습니다.

코드 구현

# 1로 만들기 문제

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

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

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

입력
26
출력
3

---