BOJ G4 17404 RGB 거리 2

17404번: RGB거리 2

---

문제 읽기

처음에 DFS로 풀었는데 어김없이 시간초과.. 처음부터 시간초과가 나지 않을까 생각하긴 했는데, 최대 1000개의 집이 각각 2번씩 선택지가 있으니까 2^1000쯤 되려나? 싶다. (시간 계산 하고 풀자 ㅠㅠ)

어떻게 하지? 하다가 아 DP구나 싶었다. 최소 비용.. 넘치는 시간.. DP는 문제를 보고 이게 DP인지 파악하는 게 제일 힘들다던데 맞는 것 같다. 감을 잃지 말자.

---

문제 풀기

첫 번째 집에 칠한 색이 각각 R, G, B일 때의 초기값을 다르게 설정하여, DP 순회를 세 번 하면 문제를 해결할 수 있다.

DP[i][j] : i번째 집을 j번째(0 : R, 1 : G, 2 : B)색으로 칠했을 때 지금까지의 최소 비용

 

즉, 첫 번째 집에 R을 칠한 경우, dp[0][0]에는 R을 칠하는 비용, dp[0][1], dp[0][2]에는 이미 R로 칠했고, 다른 색으로는 색칠할 수 없기 때문에 INF 값을 넣어준다. 그렇게 되면 두 번째 집을 칠할 때도 R, G, B를 칠하는 경우를 각각 계산해주면서 모든 경우에 대해 최소 비용으로 갱신할 수 있다.

 

마지막에는 첫 번째 집에 어떤 색을 칠했는지에 따라서 그 외 다른 두 색을 비교하여 최솟값으로 answer를 갱신해주면 된다.

 

코드를 보면 된다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G4_17404_RGB거리2 {
    static int N;
    static int[][] colorCost;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        colorCost = new int[N][3];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int j = 0; j < 3; j++){
                colorCost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = Integer.MAX_VALUE;
        int INF = Integer.MAX_VALUE - 1000;
        dp = new int[N][3];

        //0번 집이 R
        dp[0][0] = colorCost[0][0];
        dp[0][1] = INF;
        dp[0][2] = INF;
        dynamicUpdate();
        answer = Math.min(answer, Math.min(dp[N-1][1], dp[N-1][2]));

        //0번 집이 G
        dp[0][0] = INF;
        dp[0][1] = colorCost[0][1];
        dp[0][2] = INF;
        dynamicUpdate();
        answer = Math.min(answer, Math.min(dp[N-1][0], dp[N-1][2]));

        //0번 집이 B
        dp[0][0] = INF;
        dp[0][1] = INF;
        dp[0][2] = colorCost[0][2];
        dynamicUpdate();
        answer = Math.min(answer, Math.min(dp[N-1][0], dp[N-1][1]));

        System.out.println(answer);
    }

    private static void dynamicUpdate() {
        for (int i = 1; i < N; i++){
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + colorCost[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + colorCost[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + colorCost[i][2];
        }
    }

}