[백준] 1463번 - 1로 만들기

 

1463번: 1로 만들기

 

 

 

다이나믹 프로그래밍을 이용하여 해결할 수 있는 비교적 간단한 유형의 문제였다. 

 

int[] dp : 특정 수(인덱스번호)에 대하여 세 가지 연산으로 1을 만들기 위한 최소 연산 횟수

 

static int recur (int N) {
        
        if (dp[N] == null) {
            
            // MAX는 주어지는 수 X의 최대값 10^6에 대한 연산의 최대 횟수+1 값을 사용하여
            // 최종적으로 dp[N]에 값을 저장하기 위한 비교를 할 때 연산이 수행되지 않은 경우를 제외시킨다.
            
            int case1 = MAX;
            int case2 = MAX;
            int case3 = MAX;
            
            // 입력된 정수 N이 3으로 나누어지는 경우의 최솟값
            if (N % 3 == 0) case1 = recur(N/3);
            
            // 입력된 정수 N이 2으로 나누어지는 경우의 최솟값
            if (N % 2 == 0) case2 = recur(N/2);
            
            // 입력된 정수에서 1을 뺀 경우의 최솟값
            case3 = recur(N-1);
            
            // 세가지 연산의 결과를 비교하여 가장 작은 연산 횟수에 +1 한 결과를 dp[N]에 저장하고 return시킨다.
            dp[N] = Math.min(case1, Math.min(case2, case3)) + 1;
        }
        
        return dp[N];
    }

 

X = 5인 경우를 예로 들어 위 함수가 실행되는 방식을 살펴보자면

초기 dp[] (Integer형을 저장) 의 경우 dp[1]에만 0 값을 넣어주었으므로 나머지 요소들은 null상태이다. 

 

recur(5) 

연산1 :  5 % 3 != 0 이므로 case1에는 MAX(10^6)값이 그대로 담겨있다.

연산2 : 5 % 2 != 0 이므로 case2에는 MAX(10^6)값이 그대로 담겨있다.

연산3 : recur(5 - 1)  = recur(4) 

MAX(10^6), MAX(10^6), recur(4) 값 중 최소 값을 dp[5]에 저장

 

recur(4) 에서 dp[4] == null 이므로 dp[4] 값에 대한 탐색 시작

recur(4) 

연산1 : 4 % 3 != 0 이므로 case1에는 MAX(10^6)값이 그대로 담겨있다.

연산2 : 4 % 2 == 0 이므로 case2에는 recur(4/2) 값이 들어간다.

연산3 : recur(4-1) = recur(3)

 

recur(3) 

연산1 : 3 % 3 == 0 이므로 case1에는 recur(3/3) 값이 들어간다.

연산2 : 3 % 2 != 0 이므로 case2에는 MAX(10^6)값이 그대로 담겨있다.

연산3 : recur(3-1) = recur(2);

 

recur(2)

연산1 : 2 % 3 != 0 이므로 case1에는 MAX(10^6)값이 그대로 담겨있다.

연산2 : 2 % 2 == 0 이므로 case2에는 recur(2/2) 값이 들어간다.

연산3 : recur(2-1) = recur(1) = dp[1] = 0

 

이렇게 초기에 값을 넣어준 dp[1]을 만나면 앞서 함수 실행 도중에 스스로를 호출하여 실행 대기중인 함수들이 연쇄적으로 실행되어 dp[]에 값들이 저장되고 최종적으로 구하고자 하는 recur(5) 의 값을 리턴받을 수 있게 된다. 

 

 

 

 

 

Top-Down 방식

import java.util.*;

public class Main {
    
    static Integer[] dp;
    static final int MAX = 1000000;
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        dp = new Integer[N+1];
        
        dp[1] = 0;
        
        
        System.out.println(recur(N));
        
        sc.close();
    }
    
    static int recur (int N) {
        
        if (dp[N] == null) {
            
            int case1 = MAX;
            int case2 = MAX;
            int case3 = MAX;
            
            if (N % 3 == 0) case1 = recur(N/3);
            if (N % 2 == 0) case2 = recur(N/2);
            case3 = recur(N-1);
            
            dp[N] = Math.min(case1, Math.min(case2, case3)) + 1;
        }
        
        return dp[N];
    }
}

 

 

Bottom-Up 방식

Bottom-Up방식의 경우 반복문을 이용하여 dp[]의 낮은 index부터 값을 채워가며 최종적으로 dp[N]의 값을 출력하면 된다.

import java.util.*;

public class Main {
    
    static int[] dp;
    static final int MAX = 1000000;
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        dp = new int[N+1];
        
        dp[1] = 0;
        
        for (int i=2; i<N+1; i++) {
            
            int case1 = MAX;
            int case2 = MAX;
            int case3 = MAX;
            
            if (i % 3 == 0) case1 = dp[i/3];
            if (i % 2 == 0) case2 = dp[i/2];
            case3 = dp[i-1];
            
            dp[i] = Math.min(case1, Math.min(case2, case3)) + 1;
        }
        
        
        System.out.println(dp[N]);
        
        sc.close();
    }
}