[백준] 1463 - 1로 만들기 (py)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

코드

import sys

n = int(input())
arr = {}
arr[0] = 0
arr[1] = 0
arr[2] = 1
arr[3] = 1

if n > 3:
    for i in range (4, n+1):
        arr[i] = arr[i-1] + 1
        if i%3 == 0:
            arr[i] = min(arr[i],arr[i//3]+1)
        if i%2 == 0:
            arr[i] = min(arr[i], arr[i//2]+1)

print(arr[n])

풀이

DP (다이나믹 프로그래밍)을 마주치면 "일단 차근차근 해 보기" => 규칙을 찾음
1로 만들기 위해 반복하는 수를 m이라고 하자

1. n은 n-1의 m에 1을 더한 값과 같을 수 있다.
2. n이 2로 나누어떨어지면 n//2의 m에 1을 더한 값과 같을 수 있다.
3. n이 3으로 나누어떨어지면 n//3의 m에 1을 더한 값과 같을 수 있다.