BOJ 1149 RGB거리 [Java]

BOJ 1149 RGB거리

1. 문제 링크

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

2. 문제 해설

DP문제를 풀 때는 개인적으로 점화식을 세우는 것이 절반 이상이라고 생각한다. 일단 문제를 이해해보자.
문제를 읽어보면 각 집마다 빨강, 초록, 파랑 3가지 색 중 1개를 선택해서 칠할 수 있다. 또 추가적인 조건이 있는데 아래와 같다.

- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

복잡하게 쓰여있지만 결국 말하고자하는 바는 이웃한 집과는 색이 달라야한다는 것이다.

구하고자 하는 정답은 위 조건을 만족하면서 모든 집을 칠하는 비용의 최솟값이다. 조건과 구하고자 하는 바를 알았으니 이제 점화식만 세우면 된다. 점화식을 세우기 전에 한번 생각해보자. 0번 집부터 차근차근 칠해나갔다고 가정했을 때, i번 집까지 칠하는 비용은 어떻게 구할 수 있을까? 집을 3가지 색으로 칠할 수 있으니 i번 집이 빨강, 초록, 파랑일 때에 따라 나눠서 생각해볼 수 있다. 예시로 1번 집을 들어보겠다. 1번 집이 빨간색이라면, 이웃한 집끼리는 같은 색이면 안되기에 0번 집이 초록, 파랑 두 개의 색 중 하나여야 한다. 그러므로 1번 집까지 칠하는 총 비용은 아래와 같이 표현할 수 있다.

1번 집까지 칠하는 총 비용(3가지 경우의 수)
- 1번 집이 빨강일 때 총 비용 = min(0번 집이 초록일 때 총 비용, 0번 집이 파랑일 때 총 비용) + 1번 집을 빨강으로 칠하는 비용
- 1번 집이 초록일 때 총 비용 = min(0번 집이 빨강일 때 총 비용, 0번 집이 파랑일 때 총 비용) + 1번 집을 초록으로 칠하는 비용
- 1번 집이 파랑일 때 총 비용 = min(0번 집이 빨강일 때 총 비용, 0번 집이 초록일 때 총 비용) + 1번 집을 파랑으로 칠하는 비용

이런 식으로 2번, 3번 ... 반복하여 계속 쌓아나가면 최종 집인 n-1번 집이 빨강, 초록, 파랑일 때 총 비용을 구할 수 있다. 우리가 구하고자 하는 것은 n-1번 집까지 칠하는 최소 비용이므로 n-1번 집이 빨강, 초록, 파랑일 때 비용 중 최솟값이 정답이된다.

즉, 점화식은 다음과 같이 정의할 수 있다.
dp[i][j] : i번 집을 j색으로 칠했을 때, i번 집까지 칠하는데 들어간 총 비용 (j=0 -> 빨강, j=1 -> 초록, j=2 -> 파랑)

cost[i][j] : i번집을 j색으로 칠하는 비용 (j=0 -> 빨강, j=1 -> 초록, j=2 -> 파랑)

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]

3. 코드 보기

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

public class Main {
    static int n, ans;
    static int[][] cost;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        ans = Integer.MAX_VALUE;
        cost = new int[n][3];
        dp = new int[n][3];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < 3; i++) {
            dp[0][i] = cost[0][i];
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
        }

        for (int i = 0; i < 3; i++) {
            if (dp[n - 1][i] < ans) {
                ans = dp[n - 1][i];
            }
        }

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }
}