1149번: RGB거리

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

문제

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

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.

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

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-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

96

예제 입력 2

3
1 100 100
100 1 100
100 100 1

예제 출력 2

3

예제 입력 3

3
1 100 100
100 100 100
1 100 100

예제 출력 3

102

예제 입력 4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4

208

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

253

풀이

• 너무 복잡하게 생각하지 말고 이전 결과값을 이용해서 다음 결과값을 계산함을 잊지 말 것

package dynamic_programming;

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

public class Main_1149 {

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

    private static int numberOfHouse;
    private static int[][] costOfPainting;
    private static int[][] minimumCost;
    private static int[] result;

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        numberOfHouse = Integer.parseInt(st.nextToken());

        costOfPainting = new int[numberOfHouse][3];
        minimumCost = new int[numberOfHouse][3];
        result = new int[numberOfHouse];

        for (int house = 0; house < numberOfHouse; house++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            costOfPainting[house][RED] = r;
            costOfPainting[house][GREEN] = g;
            costOfPainting[house][BLUE] = b;
        }
    }

    private static void process() {
        // 초기값
        for (int color = RED; color <= BLUE; color++) {
            minimumCost[0][color] = costOfPainting[0][color];
        }

        result[0] = Arrays.stream(minimumCost[0]).min().getAsInt();

        // 점화식
        for (int house = 1; house < numberOfHouse; house++) {
            for (int finalColor = RED; finalColor <= BLUE; finalColor++) {
                int[] otherColor = findOtherColor(finalColor);
                int leftOperand = minimumCost[house - 1][otherColor[0]];
                int rightOperand = minimumCost[house - 1][otherColor[1]];

                minimumCost[house][finalColor] = costOfPainting[house][finalColor] + Math.min(leftOperand, rightOperand);
            }

            result[house] = Arrays.stream(minimumCost[house]).min().getAsInt();
        }
    }

    private static int[] findOtherColor(int targetColor) {
        int[] result = new int[2];
        int index = 0;

        for (int color = RED; color <= BLUE; color++) {
            if (targetColor != color) {
                result[index] = color;
                index++;
            }
        }

        return result;
    }

    private static void output() {
        System.out.println(result[numberOfHouse - 1]);
    }

}