백준 1463 - 1로 만들기 [DP/JAVA]

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

 

 

백준 강의 알고리즘 기초로 분류된 문제들 중 첫 DP 문제이다.(강의를 듣지는 않지만 강의에서 선택된 문제들을 순서대로 풀고 있다.)

어렵지 않은 문제이나 시간초과 때문에 고생했다.

---

사고방식

● DFS로 돌려야 한다.

-> 1) 3으로 나누거나, 2) 2로 나누거나, 3) 1을 빼거나.

위 세 행동을 반복하며, 최솟값을 구하라고 하므로 DFS라는 생각이 들었다.

● DP로 메모이제이션 해야한다.

경우의 수가 너무 많아 메모이제이션 해야하므로 DP로 해야겠다는 순서가 맞는 생각이긴 하지만 나는 DP 문제임을 알고 풀었기에... 처음부터 DP를 생각하고 풀었다.

 

그렇다면,

DFS를 어떻게 돌려야할지 경우를 나눠줘야 하는데 

1) 입력된 N이 6으로 나눠질 경우 -> dfs(n-1), dfs(n/2), dfs(n/3) 중 최솟값

2) 3으로만 나눠질 경우 -> dfs(n-1), dfs(n/3) 중 최솟값

3) 2로만 나눠질 경우 -> dfs(n-1), dfs(n/2) 중 최솟값

4) 3,2로 안 나눠져서 1을 빼는 경우 -> dfs(n-1)

로 나누었다. 

---

의문점

● 1) 6으로 나눠질 경우의 케이스를 하는 이유?

풀 때는 뭔가 느낌상 2), 3), 4) 케이스만 하면 못 구하는 부분이 있을 것 같아서 1) 6으로 나눠질 경우까지 구했다. 생각해보면 1) 번 케이스를 꼭 해줘야 한다. n이 6일 때를 예를 들어보면, 2)번 케이스에서 dfs(6-1), dfs(6/3) 중 최솟값을 구하고 3)번 케이스에서 dfs(6-1), dfs(6/2) 중 최솟값을 구한다. 1)번 케이스가 없다면 dfs(6/3), dfs(6/2) 중 최솟값을 구하는 과정이 생략된다. 

 

● dp[n+1]의 모든 값은 -1로 초기화해줘야 한다.

dp[n+1]을 만들어서 Math.min() 값을 넣어줘야 한다. 이때 dp[n+1]의 모든 값을 -1로 바꾼 후 넣어줘야 한다. dfs는 dp[n]이 이미 구해져있으면 안 해도 되므로 dp[n]이 이미 저장되어있는지를 식별해야 한다. dp[] 값들이처음에 모두 0으로 설정되어 있으므로 구분이 불가능하므로 -1로 초기화한 후, 값들을 넣어줘야 한다.

---

결론

dp[n] = Math.min(dfs(n-1), Math.min(dfs(n/3), dfs(n/2)) 이라는 식이 나온다.

(모든 dp문제가 그렇듯 이 식 구한 순간 거의 다 푼 것이다. 구현만 하면 끝이다.)

 

 

 

import java.util.Scanner;
 
public class Main {
    
    static int dp[];
    
    public static void main(String args[]) {
        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[0] = 0;
        dp[1] = 0;
 
        System.out.print(dfs(n));
        
    }
    
    static int dfs(int n){
        if(dp[n]==-1){
            if(n%6==0){
                dp[n] = Math.min(dfs(n-1), Math.min(dfs(n/3), dfs(n/2))) + 1;
            }
            else if(n%3==0){
                dp[n] = Math.min(dfs(n/3), dfs(n-1)) + 1;
            }
            else if(n%2==0){
                dp[n] = Math.min(dfs(n/2), dfs(n-1)) + 1;
            }
            else{
                dp[n] = dfs(n-1) + 1;
            }            
        }
 
        return dp[n];
    }
}