[백준 알고리즘/BOJ] 자바(java) 1149번 RGB거리

1149번: RGB거리

 

문제

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보다 작거나 같은 자연수이다.

출력

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

 

 

 

먼저 각 집을 빨강, 초록, 파랑으로 칠하는 비용을 담을 배열(cost)을 생성한다. 그 배열과 똑같은 크기로 최소 비용을 담을 배열(min)을 생성한다. cost 배열에 각 비용을 입력한 후, for문을 이용해 min배열에 최소 비용을 대입한다.

 

1번 집 빨강	1번 집 초록	1번 집 파랑
2번 집 빨강	2번 집 초록	2번 집 파랑
3번 집 빨강	3번 집 초록	3번 집 파랑

↑cost 배열

1번 집 빨강	1번 집 초록	1번 집 파랑
2번 집 빨강 + min(1번 집 초록, 1번 집 파랑)	2번 집 초록 + min(1번 집 빨강, 1번 집 파랑)	2번 집 파랑 + min(1번 집 빨강, 1번 집 초록)
3번 집 빨강 + min(2번 집 초록, 2번 집 파랑)	3번 집 초록 + min(2번 집 빨강, 2번 집 파랑)	3번 집 파랑 + min(2번 집 빨강, 2번 집 초록)

↑ min 배열 (표 속 min은 두 개의 값 중 최소값을 구하는 Math.min()을 뜻하며, 더하는 값은 cost의 배열 값이 아닌 min 배열 값이다. 단, 첫 번째 행은 i-1행과 더할 값이 없으므로 cost값)

 

1번 집을 칠하는 비용-> 1번 집을 칠하는 비용+2번 집을 칠하는 비용-> 1번 집을 칠하는 비용+2번 집을 칠하는 비용+3번 집을 칠하는 비용··· 이런 식으로 가장 번호가 낮은 집부터 채워나간다.

이 때 가까운 집과 색이 겹치지 않기 위해, i번째 집에 0(빨강)을 칠할 때는 i-1번째 집에 1(초록) 또는 2(파랑)을 칠한다.

(또한 i번째 집에 1을 칠할 때는 i-1번째 집에 0 또는 2를,

i번째 집에 2를 칠할 때는 i-1번째 집에 0 또는 1을 칠한다.)

예를 들어, min[1][2]의 값은 cost[1][2]의 비용과 그 전에 계산해뒀던 min[1][0]과 min[1][1] 중 더 작은 값 하나를 더한 값과 같다.

 

이렇게 모든 min 배열에 값을 채웠다면 min 배열의 가장 마지막 행이 N개의 색을 모두 칠한 값과 같다. 그 행에서 가장 작은 값을 출력하면 최소 비용이 된다.

package baekjoon;
import java.util.*;
import java.io.*;

public class B_1149 {
	static int N;
	static int[][] cost; // 색깔 별로 각 집을 칠하는 비용
	static int[][] min; // 집을 칠하는 최소 비용
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cost = new int[N][3];
		min = new int[N][3];
		StringTokenizer st;
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			
			cost[i][0] = Integer.parseInt(st.nextToken());
			cost[i][1] = Integer.parseInt(st.nextToken());
			cost[i][2] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(costMin());
	}
	static int costMin() {
		for(int i=0;i<N;i++) {
			if(i == 0) { // i가 0인 경우 cost값을 바로 대입
				min[i][0] = cost[i][0];
				min[i][1] = cost[i][1];
				min[i][2] = cost[i][2];
			}
			else { 
				min[i][0] = cost[i][0] + Math.min(min[i-1][1], min[i-1][2]);
				min[i][1] = cost[i][1] + Math.min(min[i-1][0], min[i-1][2]);
				min[i][2] = cost[i][2] + Math.min(min[i-1][0], min[i-1][1]);
			}
		}
		return Math.min(Math.min(min[N-1][0], min[N-1][1]), min[N-1][2]);
	}
}