[Java] 백준 1149 : RGB거리

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

1149번: RGB거리

---

모든 집을 칠하는 최솟값을 구해야 한다. 규칙은 아래와 같다. 

현재 칠할 집의 색은 앞에 칠해진 집의 색과 다르면 된다. 

 

1. RGB 값을 각각 저장한 다음 dp[][]에 이전에 칠해진 색상을 제외한 비용 중 최솟값을 구한다. 

2. dp[]에 누적 비용을 저장한다.

 

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

dp[i][0]은 현재 집을 빨간색으로 칠할 때의 누적비용을 의미한다.

현재 집을 빨간색으로 칠하려면 이전 집은 초록색이나 파란색이어야 한다.

그래서 dp[i-1][1] 과 dp[i-1][2]  즉, 빨강을 제외한  초록과 파란색을 칠했을 때의 비용을 비교해 현재 집을 빨간색을 칠했을 때의 비용을 더해서 저장한다. 

각각 색상별로 저장을 해준다음 마지막에 dp[N]의 누적금액을 비교해서 출력하면 된다. 

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static int[][] dp;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N =Integer.parseInt(br.readLine());
				
		dp = new int [N+1][3];
		
		for(int i=1;i<=N;i++) {
			String[] s = br.readLine().split(" ");
			int R=Integer.parseInt(s[0]);
			int G=Integer.parseInt(s[1]);
			int B=Integer.parseInt(s[2]);
						
			dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+R;
			dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+G;
			dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+B;
		}
		
		
		System.out.println(Math.min(dp[N][0], Math.min(dp[N][1],dp[N][2])));
		br.close(); 
		 
	}// main()
	
}// class Main