[백준] 17404번 - RGB거리 2 (Gold 4)

문제 링크

백준 17404번 - RGB거리 2 (Gold 4)

문제 설명

1번 집부터 N번 집이 순서대로 있다.
각 집을 아래 조건을 만족하도록 빨강, 초록, 파랑 중 하나의 색으로 칠하고자 한다.

• 1번 집의 색은 N번 집의 색과 다르다.
• 이웃한 집의 색은 같을 수 없다.

각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 조건을 만족하면서 모든 집을 칠하는 최소 비용을 구하시오. 단, N은 2 이상 1,000 이하이며, 각 집을 칠하는 비용은 1,000을 넘지 않는 자연수이다.

정답 코드 및 설명

N이 1,000 이하이고 각 집을 칠하는 비용이 1,000 이하이므로, 전체 비용은 1,000,000을 초과할 수 없다.
빨강을 0, 초록을 1, 파랑을 2에 대응시키자. m번 집까지 조건을 만족하도록 칠할 때 1번 집이 a색, m번 집이 b색인 경우에 드는 최소 비용을 $A_{m}[a][b]$라고 두자.

1. m = 2인 경우
   • a = b인 경우는 불가능하다. $A_{m}[a][a] = \infty$로 두자.
   • $a \neq b$인 경우 정의에 의해 $A_{m}[a][b] = cost[1][a] + cost[2][b]$
   • cost[i][x]는 i번 집을 x색으로 칠하는 비용을 뜻한다.
2. m > 2인 경우의 점화식
   • a = b인 불가능한 경우 $A_{m}[a][a] = \infty$로 두자.
   • $a \neq b$인 경우 $A_{m + 1}[a][b] = \mathrm{min}_{k \neq b}(A_m[a][k]) + cost[m + 1][b]$
   • 최솟값을 구하는 과정에서 a = k인 경우는 알아서 배제된다.

위 점화식을 바탕으로 $A_N[a][b]$를 각각 구한 후, 그 중 최솟값을 구하면 답이 된다.

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

public class BOJ17404 {
    final int INF = 1_000_001;
    int n;
    int[][] painting;
    int[][] totalCost;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        painting = new int[n][3];
        totalCost = new int[3][3];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            painting[i][0] = Integer.parseInt(st.nextToken());
            painting[i][1] = Integer.parseInt(st.nextToken());
            painting[i][2] = Integer.parseInt(st.nextToken());
        }
    }

    void solution() throws IOException {
        input();
        initialize();
        for (int i = 2; i < n; i++) {
            dp(i);
        }
        int minCost = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == i) continue;
                if (minCost > totalCost[i][j]) {
                    minCost = totalCost[i][j];
                }
            }
        }
        System.out.println(minCost);
    }

    void initialize() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == i) totalCost[i][j] = INF;
                else totalCost[i][j] = painting[0][i] + painting[1][j];
            }
        }
    }

    void dp(int curr) {
        int[][] temp = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                temp[i][j] = INF;
                for (int k = 0; k < 3; k++) {
                    if (k == j) continue;
                    if (temp[i][j] > totalCost[i][k] + painting[curr][j]) {
                        temp[i][j] = totalCost[i][k] + painting[curr][j];
                    }
                }
            }
        }
        totalCost = temp;
    }

    public static void main(String[] args) throws IOException {
        new BOJ17404().solution();
    }
}