[백준] 1149번 RGB거리 (JAVA, DP)

dp[i][j] < i 번째 집 j색깔

색깔이 0인 경우 이전 집 dp[i-1][1]과 dp[i-1][2] 중 더 비용이 적은 것에서 현재 0을 칠하는 비용을 더해주는 방식으로 

갱신해준다. 

n번째 집까지 다 칠한 경우 dp[n-1][0], dp[n-1][1], dp[n-1][2] 중에서 가장 비용이 적은 것을 출력해준다.

 

import java.util.Scanner;

public class Main {
	static int n;
	static int[][] rgb;
	static int[][] dp;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		rgb=new int[n][3];
		dp=new int[n][3];
		for (int i = 0; i < n; i++) {
			rgb[i][0]=sc.nextInt();
			rgb[i][1]=sc.nextInt();
			rgb[i][2]=sc.nextInt();
		}
		dp[0][0]=rgb[0][0];
		dp[0][1]=rgb[0][1];
		dp[0][2]=rgb[0][2];
		for (int i = 1; i < n; i++) {
			dp[i][0]=Math.min(dp[i-1][1], dp[i-1][2])+rgb[i][0];
			dp[i][1]=Math.min(dp[i-1][0], dp[i-1][2])+rgb[i][1];
			dp[i][2]=Math.min(dp[i-1][0], dp[i-1][1])+rgb[i][2];
		}
		int answer=Integer.MAX_VALUE;
		for (int i = 0; i <3; i++) {
			if(answer>dp[n-1][i])answer=dp[n-1][i];
		}
		System.out.println(answer);
	}
}