BOJ#1149 RGB거리

BOJ#1149 RGB거리

* 문제

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

* 풀이

▷ 규칙

 - 각 집은 R, G, B 3가지 색 중 한가지 색으로 칠한다.

 - 이웃한 집은 같은 색으로 칠하지 않는다.

 - 마지막 집은 R, G, B 3가지 색 중 하나이다.

 - 위 3가지 경우 중 최소값이 우리가 원하는 정답이다.

▷ dp 정의

dp[i][RED] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 RED일 때 cost

dp[i][GREEN] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 GREEN일 때 cost

dp[i][BLUE] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 BLUE일 때 cost

▷ 점화식

dp[i][RED] = min(dp[i-1][GREEN], dp[i-1][BLUE]) + RGB[i][RED]

dp[i][GREEN] = min(dp[i-1][RED], dp[i-1][BLUE]) + RGB[i][GREEN]

dp[i][BLUE] = min(dp[i-1][RED], dp[i-1][GREEN]) + RGB[i][BLUE]

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231149_RGBStreet/src

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ#1149 RGB 거리
 * https://www.acmicpc.net/problem/1149
 */

public class Main {

    static final int RED = 0;
    static final int GREEN = 1;
    static final int BLUE = 2;

    public static void main(String[] args) throws IOException {

        int N;
        int[][] RGB;
        int[][] dp; // dp[i][j] : i번째 집을 j색으로 색칠했을 때 최소 비용

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        RGB = new int[N][3];
        dp = new int[N][3];

        for (int i = 0; i < 3; i++) {

            Arrays.fill(dp[i], 0);
        }

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 3; j++) {

                RGB[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // solve
        dp[0][RED] = RGB[0][RED];
        dp[0][GREEN] = RGB[0][GREEN];
        dp[0][BLUE] = RGB[0][BLUE];

        for (int i = 1; i < N; i++) {

            for (int j = 0; j < 3; j++) {

                dp[i][j] = getMin(dp, i - 1, j) + RGB[i][j];
            }
        }

        System.out.println(Math.min(dp[N - 1][RED], Math.min(dp[N - 1][GREEN], dp[N - 1][BLUE])));

    } // main

    static int getMin(int[][] dp, int house, int exclude) {

        return exclude == RED ? Math.min(dp[house][GREEN], dp[house][BLUE]) : exclude == BLUE ? Math.min(dp[house][RED], dp[house][GREEN]) : Math.min(dp[house][RED], dp[house][BLUE]);
    }
}