백준 1463 1로만들기 Java

내가 제일 어려워하는 dp 문제들 중 쉬운 편에 속하는 문제이다.

나는 이것도 못풀었지만 최백준 님의 강의를 통해 dp 문제를 해결하는데 

대충은 감을 잡은 것 같다.

 

dp문제는 작은문제들로 큰문제를 해결하는 것이라고 한다.

1로 만들기 문제를 통해 다시 한번 정리해 볼 것이다.

 

n을 1로 만들때의 최소값을 구하기 위해

1, 2, 3 ,4 ... n까지의 최소값을 전부 구해야한다.

원래 나는 처음부터 n의 최소값을 구하는 알고리즘을 짜곤 했었는데

그건 dp에대한 이해가 부족한 것이었다.

 

문제에서는 1로만들 수 있는 세가지 방법을 알려준다.

1. 3으로 나누어떨어질 때는 나누기 3

2. 2로 나누어떨어질 때는 나누기 2

3. 빼기 1

 

3으로 나누어떨어진다고 해서 무조건 3부터 나눠버리는게 1로 만드는 최소값이 아니다.

n = 10이 그 예외이다.

 

최소값을 저장할 배열을 dp로 만들었다면

dp[0] = 0

dp[1] = 0

으로 초기화 한다. 0과 1일땐 따로 연산이 필요하지 않다.

 

그리고 문제 그대로 n/2했을 때 n/3했을 때 n-1 했을 때

가장 최소값인 것을 찾아서 dp배열에 넣어주면 된다.

가장 작은 값부터 차례대로 최소값을 구했다면

n번째 값을 구할 때 n이 3으로 나누어 떨어진다면

dp[n/3] 번째 값에 n/3을 연산한 횟수 1만 더해주면 될 것이다.

 

결국 이 문제는 dp[n/3]+1, dp[n/2]+1, dp[n-1]+1 중 최소값을 찾아서

dp[n]에 넣어주면 되는 문제였다.

dp[2]부터 차근차근 최소값을 넣어주면 dp[n]을 구할 수 있다.

 

나는 dp초보이기 때문에 우선 내가 편한 Bottom-Up방식으로 푸는법에 익숙해질 생각이다.

 

Bottom-Up 방식

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] dp = new int [n+1];
        
        dp[0] = 0;
        dp[1] = 0;
        
        for(int i=2; i<=n; i++) {
            dp[i] = dp[i-1]+1; //n이 나누어떨어지는 것과 관계없는 n-1을 일단 dp[i]에 넣어둔다.
            if(i%2 == 0) dp[i] = Math.min(dp[i/2]+1, dp[i]); 
            if(i%3 == 0) dp[i] = Math.min(dp[i/3]+1, dp[i]);
        }
        System.out.println(dp[n]);
    }

static int oneCreate(int n, int[] dp) {
        if(n==1) return 0;
        if(dp[n] > 0) return dp[n];
        dp[n] = oneCreate(n-1, dp) + 1;
        if(n%2 == 0) 
            dp[n] = Math.min(dp[n], oneCreate(n/2, dp)+1);
        if(n%3 == 0)
            dp[n] = Math.min(dp[n], oneCreate(n/3, dp)+1);
        return dp[n];
    }