[백준] 1463 1로 만들기

문제

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

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

예제 입력

2

예제 출력

1

풀이

위 그림에서 보듯 17을 1로 만드는 가능한 모든 연산들의 과정은 다음과 같다. 여기서 우리는 모든 케이스가 결국 3,2,1까지의 최소단계를 마지막으로 가진다는 사실을 알 수 있다. 따라서 3,2,1까지의 최소단계를 알면 4이상의 숫자가 가질 수 있는 최소단계를 모두 구할 수 있다.

점화식으로 나타내면 다음과 같다.

f(n) (n > 3, f(1) = 0, f(2) = 1, f(3) = 1)
= 정수 n이 1이 되기 위한 연산 사용의 최소 횟수
1) n 을 2, 3으로 나눌 수 있는 경우
f(n) = min(f(n//2), f(n//3), f(n-1)) + 1
2) n 을 2로 나눌 수 있지만 3으로 나눌 수 없는 경우
f(n) = min(f(n//2), f(n-1)) + 1
3) n 을 3로 나눌 수 있지만 2으로 나눌 수 없는 경우
f(n) = min(f(n//3), f(n-1)) + 1
4) n 을 2, 3으로 나눌 수 없는 경우
f(n) = f(n-1) + 1

n = int(input())
dp = [0] * (n+1)
if n == 1: dp[1] = 0
elif n == 2: dp[1],dp[2] = 0,1
else: dp[1],dp[2],dp[3] = 0,1,1

# Bottom up 방식
for i in range(4, n+1):
    if i % 2 == 0 and i % 3 == 0:
        dp[i] = min(dp[i//2], dp[i//3], dp[i-1]) + 1
    elif i % 2 == 0 and i % 3 != 0:
        dp[i] = min(dp[i//2], dp[i-1]) + 1      
    elif i %2 != 0 and i % 3 == 0:
        dp[i] = min(dp[i//3], dp[i-1]) + 1
    else: dp[i] = dp[i-1] + 1
print(dp[n])