1로 만들기

시간 제한이 0.15초인 것과, N이 10^6인 것으로 보여 그래프쪽으로 풀면은 시간이 초과될 것이 확실했다. 그래서 Bottom-Up 방식으로 점화식을 설계 해보고자 했다.

사용할 수 있는 연산은 아래 3가지이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나누다.
3. 1을 뺀다.

우선 다이나믹 프로그래밍에서는 dp배열에 대한 정의를 하는 것이 가장 중요하다 생각을 한다.
내가 설정한 dp배열은 다음과 같다.

dp[i]: 숫자 i를 1로 만드는 연산 횟수의 최솟값

dp[1]인 경우는 숫자 1을 1로 만드는 연산 횟수의 최솟값이다. 그러므로 dp[1]은 연산으로 표현을 못해서 0이다.
dp[2]인 경우는 숫자 2를 1로 만드는 연산 횟수의 최솟값이다. 이 경우에는 아래와 같다.

2 
- 2 - 1
- 2 // 2

첫번째 방식과 두번째 방식의 연산 횟수가 같으므로 총 연산 횟수는 1이다.
dp[3]인 경우는 숫자 3을 1로 만드는 연산 횟수의 최솟값이다. 이 경우에는 아래와 같다.

3
- 3 - 1 => 2 - 1 => 1
- 3 - 1 => 2 // 2 => 1
- 3 // 3 => 1

세번째 방식의 연산 횟수가 최솟값이므로 총 연산 횟수는 1이다.
위 3개의 예제를 보여줌으로써 dp 배열이 어떻게 동작되는지 알 수 있을 것이다.

이제 점화식을 세워보자.
dp배열은 3가지의 연산을 통해 연산 횟수를 정의할 수 있다.

1. dp[N] = dp[N//3] + 1 => 3으로 나눈 수의 연산 횟수 + 1
2. dp[N] = dp[N//2] + 1 => 2로 나눈 수의 연산 횟수 + 1
3. dp[N] = dp[N-1] + 1 => 1을 뺀 수의 연산 횟수 + 1

dp배열의 원소가 2 또는 3으로 나눠지지 않는 경우는 3번 점화식을 사용하면 된다.
그러나 2 또는 3으로 나눠지는 경우는 3번 점화식과 1번 또는 2번 점화식을 비교해 둘중에 작은 값을 dp배열의 원소로 세팅하면 된다.

그러므로 나는 소스코드를 다음과 같이 설계했다.

import sys

N = int(sys.stdin.readline().strip())
dp = [0 for _ in range(N + 2)]  # dp배열 메모이제이션을 위한 배열

# 초기값 세팅
dp[1] = 0
dp[2] = 1

for i in range(3, N + 1):
    dp[i] = dp[i - 1] + 1  # 1을 빼는 경우, 2 또는 3으로 나눠지지 않는 경우 dp[i] 셋팅
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)  # 1을 뺀 경우와 3으로 나누어 떨어지는 것 중에 작은 값을 대입
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)  # 1을 뺀 경우와 2로 나누어 떨어지는 것 중에 작은 값을 대입
print(dp[N])