다이나믹 프로그래밍: 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가 주어집니다. (1 <= X <= 30000)

출력조건

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

입출력예시

# 입력
26
# 출력
3

정답코드

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

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

# 다이나믹 프로그래밍(상향식)
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)
print(d[x])

로직

• 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그려보면 다음과 같습니다.
• 아래는 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우를 나타냅니다. 6은 5로 나누어지지 않기 때문에 생략됩니다.

• 점화식은 다음과 같습니다. 단, 나누기 연산은 해당 수로 나누어 떨어지는 경우에만 가능합니다.