[Baekjoon] 백준 1149. RGB거리- Java

 

선분 상에 이웃하고 있는 집은 서로 같은색으로 칠할 수 없다. 

 

색은 총 3가지 이며 N개의 집을 칠할 때 최소값은

 

d[N] 을 R로 칠했을 때의 비용 + d[N-1]을 G 또는 B로 칠했을 때 최소값

d[N] 을 G로 칠했을 때의 비용 + d[N-1]을 R 또는 B로 칠했을 때 최소값

d[N]을 B로 칠했을 때의 비용 + d[N-1]을 R 또는 G로 칠했을 때 최소값

 

위 3가지 경우의 수 중에 최소값이 나오는 경우 입니다. 

 

import java.util.Scanner;

public class Main {
	static int min;
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int home = scan.nextInt();
		
		int[][] cost = new int[home][3];
		int[][] d = new int[home][3];
		
		for(int i = 0; i<home; i++) {
			for(int j = 0; j<3; j++) {
				cost[i][j] = scan.nextInt();
			}
		}
		
		d[0][0] = cost[0][0];
		d[0][1] = cost[0][1];
		d[0][2] = cost[0][2];
		
		for(int i = 1; i<home; i++) {
			d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + cost[i][0];
			d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + cost[i][1];
			d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + cost[i][2];
		}
		
		int min = d[home-1][0];
		min = Math.min(min, d[home-1][1]);
		min = Math.min(min,  d[home-1][2]);
		
		System.out.println(min);
		
	
	}
	


}