[백준] 1149번 : RGB거리 - JAVA [자바]

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

인접한 집의 색은 달라야 한다.

1. r -> g, b
2. g -> r, b
3. b -> r, g

이것을 말로 설명하면
i 번째 집을 칠하는 최소 비용은 3 가지 경우를 구해야 한다.

1. r 일 때 비용 = i-1 집을 b로 칠한 비용과 g로 칠한 비용 중 적은 비용을 선택하고 + i 번째 집을 r로 칠하는 비용
2. g 일 때 비용 = i-1 집을 r로 칠한 비용과 b로 칠한 비용 중 적은 비용을 선택하고 + i 번째 집을 g로 칠하는 비용
3. b 일 때 비용 = i-1 집을 r로 칠한 비용과 g로 칠한 비용 중 적은 비용을 선택하고 + i 번째 집을 b로 칠하는 비용

즉, 현재 집을 칠하는 비용은 전의 집을 칠한 세가지 색에 따라 들었던 비용의 누적합을 구해야 하는 것이다.

n 번째 집을 r로 칠하는 비용의 점화식이다.

dp[n][r] = Math.min(dp[n-1][g], dp[n-1][b]) + cost[n][r]

public class bj1149 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        // 각 집의 색깔 비용 저장 배열
        int[][] cost = new int[N][3];
        // 누적합 비용 저장 배열
        int[][] dp = new int[N][3];
        
        // 각 색깔에 따라 집을 각각 칠하는 비용
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            int r = Integer.parseInt(split[0]);
            int g = Integer.parseInt(split[1]);
            int b = Integer.parseInt(split[2]);
            cost[i][0] = r;
            cost[i][1] = g;
            cost[i][2] = b;
        }

        // r(0), g(1), b(2) 중 어떤 걸로 칠할지에 따라 다음에 올 수 있는 경우의 수가 달라진다
        // 0 -> 1, 2
        // 1 -> 0, 2
        // 2 -> 0, 1

		// 제일 처음 집의 누적합 비용은
        // 전의 집이 없기 때문에
        // 그냥 처음 집을 칠하는 비용이다.
        dp[0][0] = cost[0][0];
        dp[0][2] = cost[0][2];
        dp[0][1] = cost[0][1];

		// 다음 집부터 마지막 N번째 집의 비용까지의 누적합을 구한다.
        for (int i = 1; i < N; i++) {
        	// r(0)로 i 번째 집을 칠할 때의 누적합
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
        	// g(1)로 i 번째 집을 칠할 때의 누적합
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
        	// b(2)로 i 번째 집을 칠할 때의 누적합
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + cost[i][2];

        }

		// 제일 마지막 집의 색깔별로 구한 누적합 비용 중 최소 비용을 찾는다.
        int min = Math.min(dp[N-1][0], dp[N-1][1]);
        int answer = Math.min(min, dp[N-1][2]);

        System.out.println(answer);

        bw.flush();
        bw.close();
        br.close();
    }
}