백준 1149번 RGB거리

주어진 규칙에 따라 모든 집을 색칠할 때 드는 최소한의 비용을 구하는 문제다.

 

단순히 각 집집마다 가장 저렴한 색상을 사용한다면 최소한의 비용을 구할 수 있다고 생각할 수 있지만, 규칙에 따른다면 불가능해진다.

 

cost[N][R] : N번째 집을 Red로 칠할 때 드는 비용이라고 하고, 각 집의 최소 비용을 수식으로 정리해보면 다음과 같다.

 

N 번째 집	Red	Green	Blue
1	cost[1][R]	cost[1][G]	cost[1][B]
2	cost[2][R] + min(cost[1][G], cost[1][B])	cost[2][G] + min(cost[1][R], cost[1][B])	cost[2][B] + min(cost[1][R], cost[1][G])
3	cost[3][R] + min(cost[2][G], cost[2][B])	cost[3][G] + min(cost[2][R], cost[2][B])	cost[3][B] + min(cost[2][R], cost[2][G])
...	...	...	...
N	cost[N][R] + min(cost[N-1][G],         cost[N-1][B])	cost[N][G] + min(cost[N-1][R],        cost[N-1][B])	cost[N][B] + min(cost[N-1][R],         cost[N-1][G])

 

즉, 식을 N번째 집에 대하여 색상에 따라 다음과 같이 정리할 수 있다.

 

Red일 경우

cost[N][R] = Math.min(cost[N-1][G], cost[N-1][B]) + cost[N-1][R]

 

Green일 경우

cost[N][G] = Math.min(cost[N-1][R], cost[N-1][B]) + cost[N-1][G]

 

Blue일 경우

cost[N][B] = Math.min(cost[N-1][R], cost[N-1][G]) + cost[N-1][B]

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt(); // 집의 수

        int[][] dp = new int[N + 1][3]; // 0:Red, 1:Green, 2:Blue

        for (int i = 1; i <= N; i++) {
            int r = in.nextInt();
            int g = in.nextInt();
            int b = in.nextInt();

            // i 번째 집을 Red로 칠할 때 최소 비용
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r;
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + g;
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + b;
        }
        int min;
        min = Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]));
        System.out.println(min);
    }
}