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

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

 

백준 1463번

 

 

 

---

사고방식 

 

백준 강의 알고리즘 기초로 분류된 문제들 중 첫 DP 문제이다. (백준 사이트에서 강의를 듣고 있지는 않지만, 백준 문제집에서 괜찮다고 판단된 문제들을 강의 예제로 넣은 것이겠다라는 생각에 강의에서 선택된 문제들을 순서대로 풀었다.) 

 

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

 

 

크게 다음과 같은 과정을 거친다. 

 

1. DFS를 돌려야 한다.

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

위 세 행동을 반복하며, 최솟값을 구하라고 하므로 DFS겠다! 라고 시작했다. 

 

2. 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 

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

닫기

풀 때는 뭔가 느낌상 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) 중 최솟값을 구하는 과정이 생략된다. 

 

의문점2 

● dp[n+1]의 모든 값은 -1로 초기화하는 이유? 

닫기

dp[n+1]을 만들어서 Math.min() 값을 넣어줘야 한다. 이때 dp[n+1]의 모든 값을 -1로 바꾼 후 넣어줘야 한다. 이유가 무엇일까?

dp[n]이 이미 구해져있다면 dfs를 하지 않아도 된다. 따라서 dp[n]에 어떠한 값이 저장되어있는지 식별해줘야 한다. dp[] 값은 처음에 모두 0으로 초기화되어 있으므로 구분이 불가능하므로, -1로 초기화한 후, 값들을 넣어주는 것이다. 물론 꼭 -1일 필요는 없고 0과 구분만 되면 된다. 다만 가장 보편적인 음수이므로 -1로 임의 지정했다. 

 

모든 dp문제가 그렇듯 점화식을 구하면 문제는 거의 끝나간다. 구현만 하면 된다. 

 

 

---

결론 

dp[n] = Math.min(dfs(n-1), Math.min(dfs(n/3), dfs(n/2)) 

 

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/3), Math.min(dfs(n-1), dfs(n/2))) + 1;
            }
            else if(n%3==0){
                dp[n] = Math.min(dfs(n-1), dfs(n/3)) + 1;
            }
            else if(n%2==0){
                dp[n] = Math.min(dfs(n-1), dfs(n/2)) + 1;
            }
            else{
                dp[n] = dfs(n-1) + 1;
            }            
        }

        return dp[n];
    }
}