BOJ 1149 - RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

dp 문제 하나를 더 풀어 봤습니다.

점화식을 세울 때 항상 1차원 배열로만 점화식을 작성했는데 2차원 배열로 작성해서 문제를 해결하는 방법이 있습니다.

이 문제는 dp의 배열을 1차원 배열로 하게 되면 R, G, B 세 가지의 색상을 나타내지 못하므로 2차원 배열을 생성해서 점화식을 작성하고 문제를 풀이합니다.

dp[i][1] = R
dp[i][2] = G
dp[i][3] = B로 만든 후에 문제를 풀이합니다.

dp[i][1] = i번째 집이 R일 때의 최소 비용
dp[i][2] = i번째 집이 G일 때의 최소 비용
dp[i][3] = i번째 집이 B일 때의 최소 비용

아래와 같은 점화식을 세울 수 있습니다.
dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + R
dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + G
dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + B

이제 처음 dp의 초기 값에 무엇을 담을지만 생각하면 됩니다. dp[1][1], dp[1][2], dp[1][3]은 첫 번째 집이니까 첫 번째 집의 비용을 그대로 담으면 되겠습니다.

풀이

import java.util.Scanner;

public class boj1149 {

    static int[][] home = new int[1001][4];
    static int[][] dp = new int[1001][4];
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        for(int i=1; i<=N; i++){
            for(int j=1; j<=3; j++)
                home[i][j] = sc.nextInt();
        }

        // R - 1, G - 2, B - 3
        for(int i=1; i<=3; i++){
            dp[1][i] = home[1][i];
        }

        for(int i=2; i<=N; i++){
            dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + home[i][1];
            dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + home[i][2];
            dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + home[i][3];
        }

        int answer = Math.min(dp[N][1], dp[N][2]);
        answer = Math.min(answer,dp[N][3]);

        System.out.print(answer);
    }
}