백준 - 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번 집의 색과 같지 않아야 한다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());
        int[][] DP = new int[N][3]; // 0: R, 1: G, 2: B

        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int R = Integer.parseInt(tokenizer.nextToken());
            int G = Integer.parseInt(tokenizer.nextToken());
            int B = Integer.parseInt(tokenizer.nextToken());

            DP[i][0] = R;
            DP[i][1] = G;
            DP[i][2] = B;
        }

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

        System.out.println(Math.min(DP[N - 1][0], Math.min(DP[N - 1][1], DP[N - 1][2])));
    }

}

• DP를 학습하면서 풀었던 문제로, 처음에 로직을 떠올렸으나 마음대로 구현이 되지 않아 시간이 조금 걸렸다.
• 문제를 꼼꼼히 읽지 않아 같은 규칙인데도 다른 규칙이라 생각하여 경우를 나누어 풀었으나 그러지 않아도 됐었다.
• 각각의 집에서 R인 경우의 최소 비용, G인 경우의 최소 비용, B인 경우의 최소 비용을 따로 구해 최솟값을 찾았다.