백준 1149번 : RGB거리

[레벨4]

 

· 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

· 입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

· 출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

· 풀이

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

public class Main {
	
	final static int r = 0;
	final static int g = 1;
	final static int b = 2;
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
 
		int N = Integer.parseInt(br.readLine());	//집의 수.
		
		int[][] cost = new int[N][3];	//집의 수(열) x 3행짜리 2차원 배열.
		
		for (int i = 0; i < N; i++) {
			//공백 기준으로 입력값을 나눠 저장.
			st = new StringTokenizer(br.readLine(), " ");
 
			cost[i][r] = Integer.parseInt(st.nextToken());
			cost[i][g] = Integer.parseInt(st.nextToken());
			cost[i][b] = Integer.parseInt(st.nextToken());
		}
		
		//안 겹치는 색등 중 최소 비용 누적.
		for (int i = 1; i < N; i++) {
			cost[i][r] += Math.min(cost[i - 1][g], cost[i - 1][b]);
			cost[i][g] += Math.min(cost[i - 1][r], cost[i - 1][b]);
			cost[i][b] += Math.min(cost[i - 1][r], cost[i - 1][g]);
		}
 
		//누적된 최소 비용 출력.
		System.out.println(Math.min(Math.min(cost[N - 1][r], cost[N - 1][g]), cost[N - 1][b]));
	}
}