백준1149_RGB거리

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

출력

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

예제 입력 

3
26 40 83
49 60 57
13 89 99

예제 출력 

96

[코드]

import java.util.Scanner;
 
public class Main {
 
    public static int color[][];
    public static int dp[][];
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        color = new int[N][3];
        dp = new int[N][3];
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                color[i][j] = sc.nextInt();
                if (i == 0)
                    dp[i][j] = color[i][j];
            }
        }
 
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j == k)
                        continue;
                    if (dp[i][j] == 0)
                        dp[i][j] = color[i][j] + dp[i - 1][k];
                    else
                        dp[i][j] = Math.min(dp[i][j], color[i][j]
                                + dp[i - 1][k]);
                }
            }
        }
 
        int min = dp[N - 1][0];
        for (int i = 0; i < 3; i++) {
            if (min > dp[N - 1][i])
                min = dp[N - 1][i];
        }
 
        System.out.println(min);
    }
}

[알고리즘]

1. 이차원배열 color에는 각 집을 각 색깔로 칠하는 비용, dp 는 최소 비용을 저장하기 위해 만들었다.

2. dp[i][j]는 i 번째 집을 j 색으로 칠하는 최소 비용을 말한다. 

3. color[i][j] 에 이전 집까지의 최소비용 dp[i-1][k]와 더했을때 최소값을 dp[i][j]에 저장한다. 같은 색깔로 칠하면 안되니까, j와 k가 같을때는 고려하지 않는다.

4. 마지막으로 dp[N-1] 행에서 가장 최소값을 구해서 출력해준다.