[ BOJ ][JAVA][17404] RGB거리 2

www.acmicpc.net/problem/17404

17404번: RGB거리 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	3202	1700	1410	53.735%

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

110

코드

/*
    RGB거리 2

    dp[i][j] = k
    : 1 ~ i번째 집까지 칠하고 i번째 집은 j색으로 칠했을때의 최소비용 = k
    첫집 RED -> 첫집의 GREEN, BLUE의 DP값을 무한대로
    첫집 GREEN -> 첫집의 RED, BLUE의 DP값을 무한대로
    첫집 BLUE -> 첫집의 RED, GREEN DP값을 무한대로
    위 3가지 경우로 나눠서 계산한 뒤
    첫집 RED -> 마지막집을 GREEN, BLUE로 칠한 DP값 중 최솟값
    첫집 GREEN -> 마지막집을 RED, BLUE로 칠한 DP값 중 최솟값
    첫집 BLUE -> 마지막집을 RED, GREEN 칠한 DP값 중 최솟값
*/
import java.io.*;
import java.util.*;

public class p17404 {
    static int n, answer;
    static int[][] arr, dp;
    static final int INF = 1000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        answer = INF;
        arr = new int[n + 1][3];
        dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[i][0] = r;
            arr[i][1] = g;
            arr[i][2] = b;
        }

        // k=0 -> RED,  k=1 -> GREEN,  k=2 -> BLUE 로 첫 집을 칠하는 경우
        for (int k = 0; k < 3; k++) {
            // RED, GREEN, BLUE로 칠하는 경우 각 색을 제외한 나머지는 INF로 초기화
            for (int i = 0; i < 3; i++) {
                if (i == k) dp[1][i] = arr[1][i];
                else dp[1][i] = INF;
            }

            // 열의 값인 0->RED, 1->GREEN, 2->BLUE 로 칠했을 때의 최소값을 의미
            for (int i = 2; i <= n; i++) {
                dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
            }

            for (int i = 0; i < 3; i++) {
                // 처음에 고른집은 정답후보에 고려하지 않는다!
                if (i != k) {
                    answer = Math.min(answer, dp[n][i]);
                }
            }
        }
        System.out.println(answer);
    }

}