[Baekjoon] 1463번: 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제 설명

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

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

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

풀이 방법 - DP

DP 기본 문제로 유명한 문제이다.

 

N = 6 이라고 가정해보자. 이 경우 호출되는 함수의 구조는 다음과 같을 것이다.

f(3), f(2), f(1) 처럼 같은 연산이 계속 반복되는 것을 볼 수 있다. 이를 바텀업 방식으로 해결하면 다음과 같다.

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int X = Integer.parseInt(br.readLine());
        int[] dp = new int[1_000_000 + 1];
        
        for (int i = 2; i < X + 1; i++) {
        // 1을 더하는 이유는 함수 호출 횟수를 더하기 위해서다.
        
            // 1을 뺐을 경우
            dp[i] = dp[i - 1] + 1;
            
            // 2로 나누었을 경우
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            
            // 3으로 나누었을 경우
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        
        System.out.print(dp[X]);
    }
}