(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 1149번 RGB거리 (실버1)

이번 문제는 각각의 집을 RGB중 하나로 칠한다고 할때, 규칙을 만족하면서 비용의 최솟값을 구하는 문제이다.

핵심은i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다라는 조건을 어떻게 구현할 것인지 였는데

어느정도 동적계획법에 익숙해져서 인지 아니면 문제가 쉬웠던 건지 조금 생각해본 후에 간단하게 풀어 낼 수 있었다.

그럼 어떻게 풀었는지 되짚어 보자.

---

규칙은 무엇인가?

우선 입력값을 보면 딱 봐도 2차원 배열 형태로 저장해야 할 것  같은 느낌이 든다.

예제 입력 1을 기준으로 살펴보자.

나는 이번 동적계획법을 2차원 배열을 사용하여 구현했다.

우선 각각의 값을 기록하기 전 초기 상태는 다음과 같을 것이다.

0	1	2
26	40	83

당연히 0번 index에는 첫행이 들어온다.

그러면 2번째 행 계산을 어떻게 해야하는지 고민해 봐야하는데, 나는 다음과 같이 생각했다.

각 셀의 값은 결국 이전 행의 다른열 값에 이번 셀의 값을 더한것 중 작은값이 들어와야 한다.

그렇게 하면 결국 각 열마다 해당 컬럼으로 시작했을때의 최소값을 구할수 있으므로, 우리는 최종적으로 만들어진 행의 컬럼을 순회하며 최소값만 가져오면 끝나는 것이다.

말로 풀어쓰면 어려우니 테이블을 채워나가 보자.

0번 열을 기준으로 살펴보았을 때, 이번 행에 들어올 값은 이번 행의 값인 49에 이전 행의 다른 열 값인 40,83을 더한 값중 작은 값이다.

즉, 49+40 과 49+83중 작은 값이 들어오면 되는것.

당연히 40을 더한값이 작을테니 테이블은 다음과 같이 채워질 것이다.

0	1	2
26	40	83
89

그럼 다음 열을 살펴보자.

이번 행의 값은 60이다.

규칙에 따라 1번 열은 들어올 수 없으니 우리는 60+26과 60+83중 선택하여야 한다.

그렇다면 86이 해당 값이 될 것이다.

0	1	2
26	40	83
89	86

이런식으로 쭉 테이블을 채워 나가면 결국 다음과 같은 값을 얻을 수 있다.

0	1	2
26	40	83
89	86	83
96	172	185

그럼 결론적으로 마지막 행인 96,172,185중 가장 작은 값인 96이 답이 되는 것이다.

그럼 코드로 살펴보자.

---

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

class Main{
    public static int n,result;
    public static int[][] arr, dp;
    public static StringTokenizer st;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][3];
        dp = new int[n][3];
        result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0] = arr[0];
        for (int i = 0; i < 3; i++) {
            result = Math.min(home(n - 1, i),result);
        }
        System.out.println(result);
    }

    public static int home(int a,int b) {
        if (dp[a][b] == 0) {
            switch (b) {
                case 0:
                    dp[a][b] = Math.min(home(a - 1, b + 1) + arr[a][b], home(a - 1, b + 2) + arr[a][b]);
                    break;
                case 1:
                    dp[a][b] = Math.min(home(a - 1, b - 1) + arr[a][b], home(a - 1, b + 1) + arr[a][b]);
                    break;
                case 2:
                    dp[a][b] = Math.min(home(a - 1, b - 2) + arr[a][b], home(a - 1, b - 1) + arr[a][b]);
                    break;
            }
            return dp[a][b];
        }
        return dp[a][b];
    }
}

앞서 설명하였듯, 2차원 배열을 선언하여 Memoization할 공간을 마련한다.

그리고 반복문을 돌면서 마지막 행의 각 열 값을 Math.min으로 비교하여 출력한다.

재귀할때는 3가지밖에 되지 않아 그냥 switch 문으로 구현하였는데, 보면 알수 있듯이 이전행인 a-1과 각각의 경우에 맞춰 자신의 행을 제외한 다른 두열의 값을 가져온다.

 

실버 1치곤 굉장히 간단하게 풀어낸 문제였던거 같다.