[백준저지] 1149번 : RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

 

1. 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입)

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출)

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] D = new int[N+1][3];
        int[][] A = new int[N+1][3];
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < 3; j++) {
                A[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= N; i++) {
            D[i][0] = (D[i-1][1] > D[i-1][2] ? D[i-1][2] : D[i-1][1]) + A[i][0];
            D[i][1] = (D[i-1][0] > D[i-1][2] ? D[i-1][2] : D[i-1][0]) + A[i][1];
            D[i][2] = (D[i-1][0] > D[i-1][1] ? D[i-1][1] : D[i-1][0]) + A[i][2];
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            if (result > D[N][i]) {
                result = D[N][i];
            }
        }
        System.out.println(result);
    }
}

D[i][j] => i번 집을 j로 칠했을 때, 1 ~ i번 집을 칠하는 비용의 최소값.

j = 0 => 빨강

j = 1 => 초록

j = 2 => 파랑

D[i][0] (i번째를 빨강으로 칠했을 때) = min(D[i-1][1], D[i-1][2]) + A[i][0]

i-1집을 초록 또는 파랑으로 칠한 비용의 최소값을 구한 뒤 i집을 빨강으로 칠하는 비용

D[i][1] (i번째를 빨강으로 칠했을 때) = min(D[i-1][0], D[i-1][2]) + A[i][1]

i-1집을 빨강 또는 파랑으로 칠한 비용의 최소값을 구한 뒤 i집을 초록으로 칠하는 비용

D[i][2] (i번째를 빨강으로 칠했을 때) = min(D[i-1][0], D[i-1][1]) + A[i][2]

i-1집을 빨강 또는 초록으로 칠한 비용의 최소값을 구한 뒤 i집을 파랑으로 칠하는 비용

위 점화식으로 각 케이스를 구한 뒤 최소값을 한번 더 체크해서 출력.