[JAVA] 백준 1149번- RGB거리

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

1149번: RGB거리

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n + 1][3];
        int[][] dp = new int[n + 1][3];

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

        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // R
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // G
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // B
        }
        System.out.println(Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]));
    }
}

 

 

dp[n][c] = n번째 집을 c 색상으로 칠하는데 필요한 최소 비용의 합

 

n번째 집까지 필요한 비용을 n번째 집이 각각 R일때, G일때, B일때를 모두 구해 그 중 최솟값을 구해야 한다.

 

 

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // R
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // G
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // B

 

위의 첫번째 예시의 dp 배열을 그려보면 다음과 같다.

 

	R	G	B
1	26	40	83
2	89	86	83
3	96	172	185

 

 

 마지막으로 n번째 집이 R일때, G일때, B일때를 비교해 가장 작은 값을 출력해준다.