[BOJ Java] 1149 : RGB 거리 ( Dynamic Programming 문제 접근 방식 )

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

1149번: RGB거리

 

제가 문제를 풀어보다가 마주한, 처음에는 해결하지 못하여 다른 DP 문제들을 여러 개 풀고 나서야 감이 잡혀서 풀어버린 Dynamic Programming 문제입니다.

 

 

Dynamic Programming 문제는, 솔직히 제가 DP 문제를 많이 풀어보지 않았어도, 직관적으로 "아 이거는 DP 문제인 것 같은데?" 라는 직감이 확 왔습니다. 이 문제도 처음 마주하자마자, Greedy 한 방법 자체가 통하지 않았다는 것을 알았기 때문에 바로 DP 로써 해결해야 하겠다는 느낌이 있었습니다.

 

DP 문제를 많이 해결해 보지 않은 사람은, 이 문제가 단순히 DP 문제로 접근해야 한다는 사실 자체만 알 수 있을 뿐, 과연 어떤 식으로 메모이제이션을 해야 할 지, Top-Down 으로 가야할지, Bottom-Up 으로 접근해야 할 지 너무 막막해 질 것입니다.

 

그래서 저는 여러 DP 문제를 풀어 보고, 막히는 문제는 다른 사람의 풀이를 보면서 겨우 해결해 가면서 DP에 대한 감을 잡았습니다. 

 

Dynamic Programming 문제를 마주했을 때 접근하는 방법

1. 먼저, 어떤 "최적 부분 구조" 를 가지며, 어떤 점화식으로써 마주할 수 있는지 찾습니다. (By Top-Down)

 

처음부터 최적으로 문제를 해결하기란 쉽지 않습니다. 

저는 일단 Top-Down 으로 문제를 먼저 분석합니다. 개인적인 경우, Top-Down 으로 먼저 접근하는 것이 Bottom-Up 으로 접근하는 것보다 수월했습니다. 그도 그럴 것이, 어떻게든 그 전 단계에서 우리가 원하는 최적을 구했다 "치고", 그 다음으로 나아갈 수 있기 때문입니다.

 

위의 문제의 경우, 이렇게 분석할 수 있습니다. 

 

1.1 맨 마지막으로 R 을 고를 경우, 그 전 단계의 G 나 B 에서 나온 최소값을 구한 다음 둘 중 더 작은 값을 택하여 R 값을 더해 줍니다.

 

1.2 맨 마지막으로 G 를 고를 경우, 그 전 단계의 R 이나 B에서 나온 최소값을 구한 다음, 둘 중 더 작은 값을 택하여 G를 골라 줍니다

 

1.3 맨 마지막으로 B 를 고를 경우, 그 전 단계의  R 이나 G 에서 나온 최소값을 구한 다음, 둘 중 더 작은 값을 택하여 B 를 골라 줍니다. 

 

일단, 그 전 단계에서 어떻게든 "구했다" 치고 그 다음 방법을 고르는 것입니다. 

이때, Top-Down 방식으로 가는 방법은, 재귀적으로 함수에 접근하며 배열에 그 값을 저장하고, 배열에 저장된 경우에는 배열에 저장된 값을 활용하는 방식입니다. 일단 DP 문제는 그 문제의 실마리 자체를 잡는 것이 중요한 문제이기에, 일단 Top-Down 방식으로 먼저 생각하는 것이 적당하다고 생각했습니다.

 

2. 만약 제한시간이 0.5초에서 추가 시간이 없다고 나온다면, 가급적 Bottom-Up 방법을 권합니다.

 

솔직히 DP 문제는 1번 단계에서 Top-Down 로 문제를 정의했다 쳐도, 결국 Bottom-Up 으로 그 사고를 발전시킬 수 있습니다. 더군다나, DP 는 Bottom-Up 으로 가는 것이 시간 복잡도 측면에서 더 유리합니다. 아무리 메모이제이션을 한다 쳐도, 재귀적으로 함수에 계속 접근하고 나오는 그 시간도 무시할 수 없다고 생각했습니다. 

 

심지어 저는, 아예 DP 문제집에 있는 문제를 풀면서도(그래서 무조건 DP 만 생각하면 되는 문제였고, 너무 자명했음에도), DP 의 Top-Down 으로 접근했을 때 시간 초과를 겪어본 적이 있기 때문입니다. 

 

반면에, Bottom-Up 방식은 맨 처음부터 배열에 값을 채워주면서 메모이제이션이 가능하고, 한 개의 함수에서 모든 것들을 처리해 배열의 가장 아랫 부분에서 의사결정을 하면 된다는 장점이 있습니다. 

 

어차피 점화식을 찾았으면, Bottom-Up 방식으로 문제를 다시 재정의하는데 있어서 그렇게 많은 시간이 걸리지 않습니다. 특히, 틀렸을 때나 시간 초과가 났을 때 어느 부분에서 문제가 되었는지 찾지 못하는 백준이라면, 더더욱 안전하게 Bottom-Up 방식으로 문제를 해결하기를 권합니다. 

 

핵심 로직

위의 방식에서 더 발전시켜 Bottom-Up 방식으로 문제를 해결해 봅시다. 

 

결국, 우리는 1번째 집만 색칠할 경우, 그냥 3개 중에 가장 작은 집만 색칠하면 됩니다. 그리고 만약에 첫번째 집을 어느 색으로 색칠할지까지 정해 줬다면, 그냥 그 색으로 색칠하면 됩니다. 

 

본격적으로 DP 가 적용되는 부분은 두 번째 집 부터입니다. 

 

두번째 집에서 최소를 고르는 경우는, 두 번째 집까지 각각 R,G,B 로 칠할 수 있는 최소값을 구한 다음에, 그 3개 중에 최소값을 구하면 될 것입니다. 

 

만약에 두 번째 집을 반드시 R로 칠한다고 가정했을 때, 첫 번째 집에서 G,B 로 칠하는 것 중에 더 작은 값을 고르고, R 를 칠하면 됩니다. 이때, G 나 B 중에 더 작은 값을 고르고 R을 칠하는 경우이므로, 2번째 집을 R로 칠하는 경우에 한해서 최소값이 될 것입니다. 

 

세번째 집을 반드시 R 로 칠한다고 가정했을 때, 두 번째 집을 G,B로 칠한 경우 중 더 작은 쪽을 고르면 됩니다. 이미 2번째 집을 G,B 로 칠했다는 가정 하에서의 최소값들을, 저장해 놓은 경우이므로 그냥 두 케이스 중 더 작은 쪽을 골라 R 을 칠하면 됩니다.

 

n 번째 집을 반드시 R 로 칠한다고 가정했을 때, n-1 번째 집을 G,B로 칠한 경우 중 더 작은 쪽을 고르면 됩니다.

 

G,B 도 똑같이 하면 되기 때문에, 각 집들을 R,G,B 로 위의 방식으로 쭉 칠한 다음에, 그냥 맨 마지막 R,G,B 케이스들에서 가장 최소값을 고르면 됩니다. 

 

아래는 문제 해결을 위한 자바 코드입니다.

public class Q1149 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] RGBTable = makeRGBTable(br,n);
        System.out.println(getMinimumValue(RGBTable,n));
    }
    static int[][] makeRGBTable(BufferedReader br, int size) throws IOException{
        int[][] RGBTable = new int[size][3];

        for(int i = 0; i < size; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            RGBTable[i][0] = Integer.parseInt(st.nextToken());
            RGBTable[i][1] = Integer.parseInt(st.nextToken());
            RGBTable[i][2] = Integer.parseInt(st.nextToken());
        }
        return RGBTable;
    }
    static int getMinimumValue(int[][] RGBTable, int size){
        int[][] minTable = new int[size][3];
        System.arraycopy(RGBTable[0], 0, minTable[0], 0, 3);

        for(int i = 1; i < size; i++){
            for(int j = 0; j <= 2; j++){
                int compareA = (j+1) % 3;
                int compareB = (j+2) % 3;
                minTable[i][j] = Math.min(minTable[i-1][compareA], minTable[i-1][compareB]) + RGBTable[i][j];
            }
        }
        return getMinimum(minTable[size-1][0],minTable[size-1][1],minTable[size-1][2]);
    }
    static int getMinimum(int a, int b, int c){
        if(a < b && a < c){
            return a;
        }else{
            return Math.min(b, c);
        }
    }
}