[ 백준 ] 17404 RGB거리 2

Link | 백준 17404번 문제 : RGB거리 2

📌 About

1149번 문제 : RGB거리에서 조건이 추가된 문제이기 때문에 우성 푸는 것이 좋다.

1번부터 N번까지의 집은 원형으로 놓여져 있으며 이웃한 집과 같은 색을 가질 수 없다.

즉, 1번은 2번과 N번, N번은 N-1번과 1번 집과 이웃한다.

1149번 문제와 동일하게 2번 집부터 탐색하며 DP를 진행하면 된다.

다만, 1번과 N번이 이웃한다는 것을 고려해야 한다.

이를 위해서 1번 집이 R, G, B를 선택하는 3번의 경우에 대해 DP를 수행한다.

만약 R을 선택한다면 G와 B의 첫번째 집값은 INF으로 설정하여 최종값으로 선택되지 못하도록 한다.

또한 마지막집을 통해 최종값을 구할 때 첫 번째 집이 선택한 색상은 배제한다.

📌 Solution

예제를 통해 이해하는 것이 쉬우므로 예제 1번을 그림으로 설명하면 다음과 같다.

위의 표는 색상에 따른 집별 요금표이다.

아래의 표들은 왼쪽부터 첫 번째 집이 R, G, B를 선택했을 때의 DP 표이다.

먼저 첫 번째 집이 선택한 색상을 제외하고는 INF로 초기화 한다.

이후의 집부터는 일반적인 DP 처럼 계산한다.

각각의 DP에서 최종값은 마지막의 집에서 최솟값을 구하면 된다.

다만, 첫 번째 집에서 선택한 색상은 제외해야 한다.

첫 번째 집에서 RED를 선택했을 때 마지막 집은 96이 될 수 없으므로 최종값은 172이다.

첫 번째 집에서 GREEN을 선택했을 때 마지막 집은 178이 될 수 없으므로 최종값은 110이다.

첫 번째 집에서 BLUE를 선택했을 때 마지막 집은 131이 될 수 없으므로 최종값은 156이다.

이 3개의 최종값 중 최솟값인 110이 최종 정답이 된다.

📌 Code

GitHub Repository

public void solve() throws IOException {
    int N = Integer.parseInt(reader.readLine());
    int[][] homes = new int[N][3];

    StringTokenizer tokenizer;
    for (int h = 0; h < N; h++) {
        tokenizer = new StringTokenizer(reader.readLine());
        for (int c = 0; c < 3; c++) homes[h][c] = Integer.parseInt(tokenizer.nextToken());
    }

    final int INF = 1_000_001;
    int minCost = Integer.MAX_VALUE;

    for (int s = 0; s < 3; s++) {
        int[][] dp = Arrays.stream(homes).map(int[]::clone).toArray(int[][]::new);
        dp[0][(s + 1) % 3] = dp[0][(s + 2) % 3] = INF;
        for (int h = 1; h < N; h++)
            for (int c = 0; c < 3; c++)
                dp[h][c] += Math.min(dp[h - 1][(c + 1) % 3], dp[h - 1][(c + 2) % 3]);
        minCost = Math.min(minCost, Math.min(dp[N - 1][(s + 1) % 3], dp[N - 1][(s + 2) % 3]));
    }

    result.append(minCost);
}