[백준 1463번 : 1로 만들기] java 풀이

1463번 : 1로 만들기 문제 링크

우리가 사용할 수 있는 연산은 총 3가지이다.

여기서 3번의 경우는 모든 1을 제외한 모든 정수에 사용할 수 있다.
하지만 1번과 2번은 모든 정수에 사용할 수는 없다. 따라서 우리는 조건문을 이용하여 경우를 따져야한다.

1) 3과 2 모두로 나누어 떨어지는 경우 : 1번 연산, 2번 연산, 3번 연산 중 최솟값 + 1
2) 3으로만 나누어 떨어지는 경우 : 1번 연산, 3번 연산 중 최솟값 + 1
3) 2로만 나누어 떨어지는 경우 : 2번 연산, 3번 연산 중 최솟값 + 1
4) 1만 뺄 수 있는 경우 : 3번 연산 + 1

최솟값을 비교할 때 3번 연산이 모두 포함되는 이유는 1을 제외한 모든 정수에 사용할 수 있기 때문이다.

문제 힌트를 보면 10의 경우를 구할 때 차례대로 9, 3, 1이 된다. 이는 즉 dp를 탐색할 때 n이 10인 경우 dp[9]의 값을 구하고, dp[9]는 dp[3]을 구하고, dp[3]은 dp[1]의 값을 이용한다. 즉 재귀 구조가 된다.

위의 구조를 보면 당연히 알 수 있는데 dp[10]은 dp[9]의 횟수에 1을 더해야 10의 연산 횟수가 된다. 따라서 점화식을 보면 어떤 경우든 1을 더해야한다.

🔑java 풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int dp[];
    static int min(int n){
        if(dp[n]==-1){
            if(n%3==0&&n%2==0) { //2와 3으로 모두 나뉘어지면
                dp[n]=Math.min(Math.min(min(n/3),min(n/2)),min(n-1))+1;
            }
            else if(n%3==0){//3으로만 나뉘어지면
                dp[n]=Math.min(min(n/3),min(n-1))+1;
            }
            else if(n%2==0){
                dp[n]=Math.min(min(n/2),min(n-1))+1;
            }
            else{
                dp[n]=min(n-1)+1;
            }
        }
        return dp[n];
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        dp=new int[n+1];

        for(int i=0; i<n+1; i++)
            dp[i]=-1;

        dp[1]=0;
        if(n==1){
            System.out.println(dp[1]);
            return;
        }
        dp[2]=1;
        System.out.println(min(n));
    }
}