1로 만들기

링크: https://www.acmicpc.net/problem/1463
분류: DP, 동적 프로그래밍
레벨: Silver 3

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

예제 입력

예제 출력

풀이

이 문제는 전형적인 DP(Dynamic Programming) 유형이다.
예시의 10은 10 -> 9 -> 3 -> 1 의 순서로 계산하는 것이 최소 계산 방법이다.
이 때 10은 9의 DP 결과를 사용하는 것을 알 수 있고,
9는 다시 3의 DP 결과를 사용하는 것을 알 수 있다.
이렇게 앞서 구한 결과값을 저장한 후 사용하는 것이 DP이다.
따라서 list를 차례로 채워주고, 마지막에 결과에 해당하는 값을 출력하는 작업이 필요하다.
먼저, 2 또는 3으로 나누어지지 않는 값의 경우 아래와 같이 1을 빼주어야 한다.
아래는 i-1 번째 수로부터 i 번째 수를 계산하는 것이므로 1을 더해주었다.

import sys
input = sys.stdin.readline

X = int(input())
dp = [0] * (X + 1)

for i in range(2, X+1):
    dp[i] = dp[i - 1] + 1

위와 같이 dp라는 이름의 list를 초기화할 때, index와 계산하는 수를 맞춰주기 편하게 0 번째는 건너 뛰었다.
즉, 첫 번째 index는 0, 두 번째 index는 1에 해당하므로 X + 1 크기의 list를 만들었다.
1을 빼는 경우를 생각한 후에는 2로 나누어지는 경우와 3으로 나누어지는 경우를 생각해야 한다.
2(또는 3) 로 나누어질 경우에, 1을 빼는 경우와 2(또는 3)로 나누는 경우 중 어떤 것이 최소값인지 판단해야 한다.
예를 들어 8의 경우, 2로 나누어진다. 만약 8에서 1을 뺀다면 7의 DP 결과를 사용할 것이다.
그렇다면 8 -> 7 -> 6 -> 2 -> 1 순서로 계산될 것이다.
1을 빼지 않고 2로 나눈다면 8 -> 4 -> 2 -> 1 순서로 계산된다.
4의 DP 결과를 사용하고 그 횟수에 1을 더해준 값이, 1을 뺀 후 7의 DP 결과를 사용하는 경우보다 계산 횟수가 적다.
마지막으로는 X에 대한 결과를 출력한다.
아래와 같이 코드를 작성할 수 있다.

import sys
input = sys.stdin.readline

X = int(input())
dp = [0] * (X + 1)

for i in range(2, X+1):
    dp[i] = dp[i - 1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[X])