[DP] 다이나믹 프로그래밍 (2) 실전 문제 - 1로 만들기 ⭐

이코테 p.217 실전 문제 - 1로 만들기

입력 예시

26

출력 예시

3

교재 소스코드

• 해당 문제는 잘 알려진 DP 문제
• 함수가 호출되는 과정을 도식화해보면 동일한 값을 구하는 동일한 함수가 중복으로 호출되는 것을 알 수 있음 ➡️ DP 적용
• 바텀업 방식으로 구현
  • 2부터 X까지 차근차근 해당 수를 만들 수 있는 최소 연산 횟수를 기록해 나가는 방식
  • 1을 뺐을 때, 2로 나누었을 때, 3으로 나누었을 때, 5로 나누었을 때 중에서 최소가 되는 연산 횟수를 현재의 연산 횟수로 기록해야 함
  • dp[i]는 숫자 i를 만들 수 있는 최소 연산 횟수를 의미
  • 점화식으로 표현하자면, a(i) = min(a(i - 1), a(i / 2), a(i / 3), a(i / 5)) + 1
  • +1을 해주는 이유는 연산의 횟수를 구하는 문제이기 때문

# 입력받기
x = int(input())

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

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

print(dp[x])