[백준] 1149. RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

잘못 생각하면 그리디 알고리즘을 떠올릴 수 있다. 1번째 집부터 접근하여 3가지 색 중 가장 비용이 적은 색으로 칠하고, 2번째 집에 접근하여 1번째 집이 사용한 색을 제외하고 비용이 적은 색으로 칠하는 방식이다. 그러나 이는 잘못된 방법이다.

 

반례는 다음과 같다. 각 집이 빨간색, 초록색, 파란색으로 집을 칠하는 비용이 아래와 같다. 

1번 집	1	100	103
2번 집	1	103	200
3번 집	100	1	103

 

그리디로 풀면 1번 집은 빨간색(1), 2번 집은 초록색(103), 3번 집은 빨간색(100)으로 집을 칠한다. 따라서 총 204의 비용이 든다.

그러나 1번 집은 초록색(100), 2번 집은 빨간색(1), 3번 집은 초록색(1)으로 집을 칠하여 총 102의 비용이 드는 것이 최소 비용이다. 

 

즉 당장의 최선의 선택이 전체적으로 봤을 때 최선의 선택이 아니다!

 

결론적으로 이 문제는 dp로 풀어야 한다. cost 배열이 각 집을 빨간색, 초록색, 파란색으로 칠하는데 드는 비용이고, totalMinCost가 i번째 집까지 빨간색, 초록색, 파란색으로 칠하는데 드는 최소 비용이라고 할 때 점화식은 다음과 같다.

// i번째 집을 빨간색으로 칠하는 경우
totalMinCost[i][0] = min(totalMinCost[i - 1][1], totalMinCost[i - 1][2]) + cost[i][0]

// i번째 집을 초록색으로 칠하는 경우
totalMinCost[i][1] = min(totalMinCost[i - 1][0], totalMinCost[i - 1][2]) + cost[i][1]
 
// i번째 집을 파란색으로 칠하는 경우
totalMinCost[i][2] = min(totalMinCost[i - 1][0], totalMinCost[i - 1][1]) + cost[i][2] 

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 시간복잡도: 이차원 배열 = 3 * N = 3,000
public class Main {

    static int n;
    static int[][] cost;
    static int[][] totalMinCost;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        cost = new int[n][3];
        totalMinCost = new int[n][3];

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

        totalMinCost[0][0] = cost[0][0];
        totalMinCost[0][1] = cost[0][1];
        totalMinCost[0][2] = cost[0][2];

        for (int i = 1; i < n; i++) {
            // i번째 집을 빨간색으로 칠하는 경우(i-1번째 집은 초록, 파랑 중 총 비용이 더 적은 색으로)
            totalMinCost[i][0] = Math.min(totalMinCost[i - 1][1], totalMinCost[i - 1][2]) + cost[i][0];
            // i번째 집을 초록색으로 칠하는 경우(i-1번째 집은 빨강, 파랑 중 총 비용이 더 적은 색으로)
            totalMinCost[i][1] = Math.min(totalMinCost[i - 1][0], totalMinCost[i - 1][2]) + cost[i][1];
            // i번째 집을 파란색으로 칠하는 경우(i-1번째 집은 빨강, 초록 중 총 비용이 더 적은 색으로)
            totalMinCost[i][2] = Math.min(totalMinCost[i - 1][0], totalMinCost[i - 1][1]) + cost[i][2];
        }

        System.out.println(Math.min(totalMinCost[n - 1][0], Math.min(totalMinCost[n - 1][1], totalMinCost[n - 1][2])));
    }
}