[백준 17404번] RGB거리 2

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

 

 

 

package dp;

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

public class DP17404 {
    static final int INF = Integer.MAX_VALUE; // 큰 값
    static int N;
    static int[][] cost; // cost[i][c] : i번째 집을 c색으로 칠하는 비용 (c: 0=R,1=G,2=B)
    static int[][] dp;   // dp[i][c] : i번째 집까지 칠했을 때, i번째 집을 c색으로 칠한 최소 비용

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        cost = new int[N + 1][3];
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i][0] = Integer.parseInt(st.nextToken()); // R
            cost[i][1] = Integer.parseInt(st.nextToken()); // G
            cost[i][2] = Integer.parseInt(st.nextToken()); // B
        }

        int ans = INF;

        // 첫 번째 집의 색을 0(R), 1(G), 2(B) 중 하나로 고정해서 세 번 실행
        for (int firstColor = 0; firstColor < 3; firstColor++) {
            dp = new int[N + 1][3];

            // 초기화: 첫 번째 집 색을 firstColor로 강제, 나머지는 불가능(INF)
            for (int c = 0; c < 3; c++) {
                if (c == firstColor) dp[1][c] = cost[1][c];
                else dp[1][c] = INF;
            }

            // DP 채우기
            for (int i = 2; i <= N; i++) {
                dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
            }

            // 마지막 집은 첫 번째 집과 다른 색이어야 함 (문제 조건이 그럼)
            for (int lastColor = 0; lastColor < 3; lastColor++) {
                if (lastColor == firstColor) continue; // 같은 색이면 스킵
                ans = Math.min(ans, dp[N][lastColor]);
            }
        }

        System.out.println(ans);
    }
}

 

전형적인 DP 문제이다.

 

핵심은 첫 번째 집과 마지막 집의 색을 비교하는 것이다.

 

INF를 선언하는 이유는 같은 색이 연속해서 선택되는 경우를 배제하기 위해서다. 따라서 프로그램은 첫 번째 집을 세 가지 색으로 각각 시작해 보면서 경우의 수를 나눠 진행한다. 마지막 집에서는 첫 번째 집과 같은 색이면 건너뛰고, 다른 색이면 Math.min에 넣어 최소 비용을 선택하는 방식으로 결과를 도출한다.