P.17404 RGB거리 2

코드

package Baekjoon.Class;

import java.io.*;
import java.util.Arrays;

public class P_17404 {

    static final int MAX = 1000 * 1000 + 1;

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

        int n = Integer.parseInt(br.readLine());
        int[][] houses = new int[n][n];
        for (int i = 0; i < n; i++) houses[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[][] dp = new int[1001][3];
        int ans = MAX;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == j) dp[0][j] = houses[0][j];
                else dp[0][j] = MAX;
            }

            for (int j = 1; j < n; j++) {
                dp[j][0] = Math.min(dp[j - 1][1], dp[j - 1][2]) + houses[j][0];
                dp[j][1] = Math.min(dp[j - 1][0], dp[j - 1][2]) + houses[j][1];
                dp[j][2] = Math.min(dp[j - 1][0], dp[j - 1][1]) + houses[j][2];
            }

            for (int j = 0; j < 3; j++) {
                if (i != j) ans = Math.min(ans, dp[n - 1][j]);
            }
        }

        bw.write(Integer.toString(ans));
        bw.flush();
    }
}

코드 설명

전체적인 dp 점화식은 이전 시리즈 문제인 RGB거리 1과 같다.

2022.04.16 - [코딩테스트_JAVA/백준] - P.1149 RGB거리

P.1149 RGB거리

 

한 번 더 확인해야 할 것은 0번째 집의 색과 n-1번째 집의 색이다.

0번째 집의 색을 고정시켜놓는다면 n - 1번째 집의 색을 결정할 수 있다.

위 RGB 거리 식의 시간복잡도는 1000 * 3인데 0번째 집의 색을 빨강, 초록, 파랑으로 고정시켜놓는다면 3 * 1000 * 3의 시간이 걸리므로 0.5초 내에 해결 가능하다.

 

가장 외부의 for문의 i는 각각의 색을 의미한다. 

i == 0 -> RED

i == 1 -> GREEN

i == 2 -> BLUE

 

내부 for문 중 첫 번째 for문은 0번째 집의 색을 의미한다.

i == j일 경우 해당 색을 선택하고, i != j일 경우 MAX값(1000 * 1000 + 1)으로 설정하여 이후 dp의 과정에서 선택되지 않도록 한다.

두 번째 for문은 1부터 n - 1번째 집의 색을 의미하고, 해당 알고리즘은 RGB거리에 설명되어있다.