[Java]백준1149_RGB거리

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

1149번: RGB거리

 

[문제]

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

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

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

[입력]

3                      // 집의 개수
26 40 83            // RGB 비용
49 60 57
13 89 99

 

[출력]

96

 

[풀이]

처음에는 그리디알고리즘으로 접근하였다.

첫번째 집부터 비용이 최소인 색상을 정하고, boolean 배열에 선택한 색상을 저장해두었다.

그 다음집부터는 배열이 false이면서 최소인 색상을 선택해 누적합하였다.

예제 1~4번까지는 맞았지만 예제 5번에서 다른값이 나왔다.

 

그래서 첫 선택이 최소값이 아닌, 모든 경우의 수를 고려해야한다는것을 깨닫고 DP로 풀었다.

첫행을 제외하고, n번째 행은 n-1행에서 자신을 제외한 색 중 최소값을 누적합한다.

 

 

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

public class BJ1149_RGB거리 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine());
		
		int[][] color = new int[N][3];
		int[] select = new int [N];
		
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				color[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		
		for(int i=1; i<N; i++) {
			color[i][0]+=Math.min(color[i-1][1],color[i-1][2]);		//R : i-1항의 G와 B중 최소값 더해준다.
			color[i][1]+=Math.min(color[i-1][0],color[i-1][2]);		//G
			color[i][2]+=Math.min(color[i-1][0],color[i-1][1]);		//B
		}
		
		int temp = Math.min(color[N-1][0], color[N-1][1]); //마지막행 R G B 최소값 비교
		int ans=Math.min(temp, color[N-1][2]);	
		
		System.out.println(ans);
		
	}

}