[Java] 백준 17404번 : RGB거리 2

1. 문제

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

17404번: RGB거리 2

 

 

 

2. 풀이 과정

1 => N번째 집을 차례대로 색을 칠한다. 각자 자신의 앞의 집의 색깔만 피하면 된다.

단, 마지막 집은 첫 번째 집의 색깔도 고려해야하기 때문에 처음부터 첫 번째 집의 색에 따라 나눠 계산했다.

 

 

첫 번째 집 색에 따라 R[], G[], B[]를 만들어서 값을 업데이트해갔다. 이는 Dynamic Programming을 사용한 풀이 방법이라 볼 수 있다.

 

예를 들어 R[]에서 현재 집의 색을 Red로 칠할 경우, 이 전의 집을 Green으로 칠했을 때인 R[1]과 Blue로 칠했을 때인 R[2] 중 더 작은 값을 선택해서 현재 집을 Red로 칠할 때 값을 더해서 업데이트한다.

 

 

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

public class Main {
	public static void update(int[] arr, int[] price) {
		int n1 = Math.min(arr[1], arr[2]);
		int n2 = Math.min(arr[0], arr[2]);
		arr[2] = Math.min(arr[0], arr[1])+price[2];
		arr[0] = n1+price[0];
		arr[1] = n2+price[1];
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		final int INF = 999_999_999;
		
		int n = Integer.parseInt(br.readLine());
		int R[] = new int[3], G[] = new int[3], B[] = new int[3];
		
		//초기 세팅
		st = new StringTokenizer(br.readLine());
		R[0] = Integer.parseInt(st.nextToken());
		G[1] = Integer.parseInt(st.nextToken());
		B[2] = Integer.parseInt(st.nextToken());
		
		R[1] = R[2] = G[0] = G[2] = B[0] = B[1] = INF;
		
		//값 읽어들이면서 update
		int price[];
		for(int i=1;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			price = new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
			update(R, price);
			update(G, price);
			update(B, price);
		}
		System.out.println(Math.min(Math.min(Math.min(R[1], R[2]), Math.min(G[0], G[2])), Math.min(B[0], B[1])));
	}
}