백준 1463 - 1로 만들기

 

정수 N이 주어졌을 때, 세가지 방법의 연산으로 1로만드는 최소 방법의 수를 구하는 문제이다.

 

먼저 상태와 가장 작은문제를 종료하기 위한 조건은 직관적이다 --> 상태 :N , 종료조건 N ==1 

 

이제 문제를 풀기위한 점화식을 생각해보자.

 

먼저, 큰 문제 D[N]을 작은 문제로 쪼개서 생각해보자. (D[N] => N을 만드는 가장 최소의 경우의 수 return)

 

**계산하는 과정에서 변하지 않는것  -> 각 수를 최소방법으로 1로만드는 경우의 수 

ex D[2] : 2 ->1 (/2) ,D[3] :3 -> 1 (/3) , D[4] : 4 -> 2 -> 1 (/2) 

**기억해야할 것 : 각 단계에서 1로만드는 최소의 경우의 수  

 

그렇다면 D[N]을 최소의 경우로 1로만드는 조건은 N을 -> N/3 or N/2 or N-1로 만드는 연산 1개와 

1이 될 때까지 나누기 3을 하던, 나누기 2를 하던 빼기 1을 하던 각 나머지 연산 중 가장 작은 것의 더하기 일 것이다.

 

가령 10이라면, 10 -> 5 -> 4 -> 2 -> 1 의 4단계 10 -> 9 -> 3 -> 1 의 3단계가 있다.

여기서 10을 /2해서 5로만드는 방법 1 + 나머지 5가 1이되는 최소 경우의 수 (3) = 총 4단계

             10에 -1해서 9로 만드는 방법 1 +  나머지 9가 1이되는 최소 경우의 수 (2) = 총 3단계 

이 두개 중 그냥 가장 작은 것을 고르면 그만이다. 

따라서 점화식은

 

D[N] = min(D[N/3],D[N/2],D[N-1]) +1 이다.

 

구현

탑다운

public class Main {
    public static int[] d;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        d = new int[n+1];

        System.out.print(toOne(n));


    }
    public static int toOne(int n){
        if(n == 1) return 0;
        if(d[n] >0) return d[n];
        d[n] = toOne(n-1)+1;
        if(n % 2 ==0){
            int temp = toOne(n/2)+1;
            if(temp < d[n]) d[n] =temp;
        }
        if(n % 3 ==0){
            int temp = toOne(n/3)+1;
            if(temp < d[n]) d[n] =temp;
        }


        return d[n];
    }

}

빠텀업

   public static int[] d;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        d = new int[n+1];
        d[1]=0;
        for(int i=2; i<=n ;i++){
            d[i] = d[i-1]+1;
            if(i % 2 ==0){
                int tmep = d[i/2]+1;
                d[i] = d[i] < d[i/2]+1 ? d[i]:d[i/2]+1;
            }
            if(i %3 ==0){
                int temp = d[i/3]+1;
                d[i] = d[i] <d[i/2]+1 ? d[i]:d[i/3]+1;
            }
        }
        System.out.print(d[n]);


    }