[Baekjoon Online Judge] 1149번: RGB거리

1149번: RGB거리

요구사항

 - RGB 거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
 - 집은 R, G, B 중 하나의 색으로 칠해야 한다. 각각의 집을 R, G, B 로 칠하는 비용이 주저였을 때,
아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구한다.

 

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

입력

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

출력

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

---

 조건을 잘 살펴보면, 근접한 집들은 색이 겹칠 수 없다. 그렇기 때문에 시작하는 집 (i == 0 일 때) 을 제외하면 현재 집의 색과 다른 색을 가진 집의 RGB 가중치 값 중 가장 작은 값을 더해주며 dp 테이블을 채워나간다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Baekjoon1149 {

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());
        int[][] rgbArray = new int[n][3];
        int[][] dp = new int[n][3];

        for (int i = 0; i < n; i++) {
            String[] rgb = bufferedReader.readLine().split(" ");
            rgbArray[i][0] = Integer.parseInt(rgb[0]); // red
            rgbArray[i][1] = Integer.parseInt(rgb[1]); // green
            rgbArray[i][2] = Integer.parseInt(rgb[2]); // blue
        }

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

        bufferedWriter.write(String.valueOf(Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2])));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 dp 테이블을 모두 채운 후, 마지막에 가장 적은 비용이 들어 있는 수를 출력해준다.