[Java][백준][1149] RGB 거리

문제

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

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

입력

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

출력

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

 

생각

아래의 두 문제보다는 접근이 괜찮았다. 일단 D[i]를 뭘로 잡아야할까? D[i]는 i번째 집을 칠할 때 까지의 비용의 최솟값이다. 하지만 i번째 집을 칠할 수 있는 경우의 수는 3개이므로 2차원 배열로 만들자.

따라서 D[i][j]: j(0:빨강, 1:초록, 2:파랑) 번째 색으로 i번째 집을 칠할 때 까지의 비용의 최솟값이라고 정하자.

또한 S[i][0]: i번째 집을 빨강색으로 칠하는데 비용, S[i][1]: i번째 집을 초록색으로 칠하는데 비용, S[i][2]: i번째 집을 파랑색으로 칠하는데 비용이라고 하자.

 

초기값은 D[1][0] = S[1][0], D[2][0] = S[2][0], D[3][0] = S[3][0] 이다. D[2][0] 은 어떻게 될까? D[2][0]은 빨강색으로 칠하므로 1번째 집을 빨강색으로 칠해서는 안된다. 따라서 D[2][0] = Math.min(D[1][1], D[1][2]) + S[2][0] 이 될 것이다. 이 생각만 하면 바로 점화식이 나온다. 바로 코드로 보자

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        int[][] S = new int[n+1][3];
        int[][] dp = new int[n+1][3];
        
        for(int i=1; i<=n; i++) {
            String[] str = br.readLine().split(" ");
            for(int j=0; j<3; j++) {
                S[i][j] = Integer.parseInt(str[j]);
            }
        }
        
        dp[1][0] = S[1][0]; dp[1][1] = S[1][1]; dp[1][2] = S[1][2];
        
        for(int i=2; i<=n; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + S[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + S[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + S[i][2];
        }
        
        int tmp = Math.min(dp[n][0], dp[n][1]);
        
        System.out.println(Math.min(tmp, dp[n][2]));
     }
 
}