DP로 최단 시간 찾기

백준 1463번을 DP를 이용해 Java로 풀어봤다.
마지막에 첨언하겠지만 처음에는 DP로 어떻게 해야할지 모르겠어서 BFS로 풀었더니 이것도 되긴 한다. 하지만 DP를 공부 중이니까 DP에 초점을 맞춰보자.

잡종 코드

내가 DP가 아직 익숙하지 않고, 정확히 어떻게 구현하는지도 잘 모른 채 아이디어만 추상적으로 아는 상태에서 코드를 짜봤는데 돌아가기도 하고 실제로 맞기도 했다. 근데 아무리 봐도 DP의 아이디어를 구현한 코드같지는 않다. 근본이 없는 그냥 마구잡이 코드 같은데 나중에 다시 보게 되면 이게 무슨 혼종인가 하며 깨달을 날을 막연히 기대하며 일단 첨부한다.

static void DP(int n){
        if(n%3==0 && (dp[n/3]==-1 || dp[n]+1<=dp[n/3])) {
            dp[n / 3] = dp[n] + 1;
            DP(n/3);
        }
        if(n%2==0 && (dp[n/2]==-1 || dp[n]+1<=dp[n/2])) {
            dp[n / 2] = dp[n] + 1;
            DP(n/2);
        }
        if(n>=2 && (dp[n-1]==-1 || dp[n]+1<=dp[n-1])) {
            dp[n - 1] = dp[n] + 1;
            DP(n-1);
        }

        if(dp[1]!=-1)   return;
    }

위의 DP(n) 메소드를 main 함수에서 호출한 뒤 dp[1]을 출력하면 답이 나오긴 했다. 내가 짰지만 나도 이게 대체 뭔지 모르겠다.

Top-down과 Bottom-up

아직 정확히 알지는 못하지만 DP를 이용할 때 방향성에 따라서 Top-down과 Bottom-up 방식으로 나뉘는 것 같다.

내가 참고했던 코드는 Bottom-up을 사용했는데 난 이게 더 DP 개념과 연결돼서 잘 이해가 되길래 이거로 선택했다. 후에 다른 문제들을 만나게 될 때 상황에 따라 두 방식 중 선택을 해야하는 경우가 있을지는 모르겠지만, 일단 Bottom-up을 익혀서 사용해보려 한다.

말 그대로 작은 값들부터 먼저 계산하고 위로 올라가는 방향성이다.
dp[1] 은 시작점이니까 당연히 0으로 초기화 해주고 시작한다. 그러고 나서 dp[2] 부터 dp[n] 까지 계산해주면 된다.

이 때 먼저 더 작은 수를 다루게 될 -1 연산부터 하고, 그 후에 2로 나누기와 3으로 나누기를 진행하면 된다.
코드로 확인해보자.

static int DP(int n) {
        dp[1] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; // 1 빼기
            if (i % 2 == 0) // 2로 나누기
                dp[i] = Math.min(dp[i], dp[i/2]+1); // 기존에 있던 값보다 더 작으면 바꿔주자
            if (i % 3 == 0) // 3으로 나누기
                dp[i] = Math.min(dp[i], dp[i/3]+1); // 기존에 있던 값보다 더 작으면 바꿔주자
        }
        return dp[n];
    }

즉 dp[n]에 n의 숫자가 1로 만들어지는 데 몇 번의 연산이 필요한지 저장되는 것이다.

아래는 DP를 이용한 전체 코드다.

import java.util.*;
import java.io.*;

public class boj1463 {
    static int n, dp[] = new int[1000001];

    static int DP(int n) {
        dp[1] = 0;

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

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bfr.readLine());
        System.out.println(DP(n));
    }
}

BFS로도 풀리던데요

최소 연산 횟수를 구하라길래 BFS로도 될까 싶어서 먼저 생각난 BFS 풀이를 시도했더니 통과했다. 물론 코드의 길이는 훨씬 길어진다. 하지만 익숙한 코드라서 딱히 더 오래 걸린다거나 그렇진 않다.

아래는 BFS로 풀었을 때 제출한 코드다.

import java.util.*;
import java.io.*;

public class boj1463 {
    static int n, dp[] = new int[1000001];

    static void bfs(int n) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});

        while (!q.isEmpty()) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int[] cur = q.poll();
                int curNum = cur[0];
                int curCnt = cur[1];

                if (curNum == 1) return;

                /** 3으로 나누기 */
                if (curNum % 3 == 0 && dp[curNum / 3] == -1) {
                    dp[curNum / 3] = curCnt + 1;
                    q.add(new int[]{curNum / 3, curCnt + 1});
                }

                /** 2로 나누기 */
                if (curNum % 2 == 0 && dp[curNum / 2] == -1) {
                    dp[curNum / 2] = curCnt + 1;
                    q.add(new int[]{curNum / 2, curCnt + 1});
                }

                /** 1 빼기 */
                if (dp[curNum - 1] == -1) {
                    dp[curNum - 1] = curCnt + 1;
                    q.add(new int[]{curNum - 1, curCnt + 1});
                }
            }
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bfr.readLine());
        for (int i = 0; i < 1000001; i++)
            dp[i] = -1;
        dp[n] = 0;

        bfs(n);
        System.out.println(dp[1]);
    }
}

오늘 배운 것

시험 때 무슨 문제인지 뻔히 보이지만, 그 풀이로 못 풀겠으면 일단 풀 줄 아는 방법으로라도 풀어보자