[BOJ] - RGB거리 / 1149번 (Java)

[BOJ] - RGB거리 / 1149번 (Java)

[BOJ] - RGB거리 / 1149번 (Java)

1. 문제 접근

N개의 집에 대해 인접한 집이 서로 다른 색으로 칠해지도록 하는 경우의 수 중, 최소 비용을 구하면 된다.

 

1번 집의 경우는 3가지 색 모두 사용하여 칠할 수 있다.

 

2번 집의 경우 1번 집의 색이 아닌 2개의 색 중 하나를 골라 칠할 수 있다.

 

이후 집들도 모두 동일하다.

 

따라서, 각 집에 대해 특정 색으로 칠했을 때의 비용을 누적해가면서 최적해를 찾으면 되는 DP문제다.

 

2차원 DP 동적 테이블이 필요하다.

 

테이블의 크기는 3행(R, G, B) N열이 된다.

// 0행: R
// 1행: G
// 2행: B
dp = new int[3][N];

첫 집의 경우는 모든 색 칠할 수 있으므로 다음과 같이 초기화 한다.

// 초기 세팅
st = new StringTokenizer(br.readLine().trim());
dp[0][0] = Integer.parseInt(st.nextToken());
dp[1][0] = Integer.parseInt(st.nextToken());
dp[2][0] = Integer.parseInt(st.nextToken());

이후, 2번째 집 부터 N 번째 집까지 앞집이 칠하지 않은 색 중에 최소값을 더해가며 누적 비용을 구하면된다.

dp[0][idx] = Math.min(dp[1][idx-1], dp[2][idx-1]) + redCost;
dp[1][idx] = Math.min(dp[0][idx-1], dp[2][idx-1]) + blueCost;
dp[2][idx] = Math.min(dp[0][idx-1], dp[1][idx-1]) + greenCost;

최종적으로 N번째 집까지 칠하고 난 뒤의 3개의 누적합 중에 최소를 선택하면된다.

---

2. 코드

package boj;

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

/**
 * [BOJ] - RGB거리 / 1149번 
 * @author JinHxxxxKim
 * 
 * Dynamic Progrmming
 * 
 * 각 집을 색칠하는 방법: 3가지 
 * 	- R: 이전 집을 G, B로 칠하는 비용 중 최소 + 자신을 R로 칠하는 방법
 * 	- G: 이전 집을 R, B로 칠하는 비용 중 최소 + 자신을 G로 칠하는 방법
 * 	- B: 이전 집을 R, G로 칠하는 비용 중 최소 + 자신을 B로 칠하는 방법
 * 
 * 이후 N번 째 집까지 칠한 뒤, R, G, B 중 최소값 출력
 */
public class Sol_1149 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st;

	static int[][] dp;
	static int N; // 집의 개수
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine().trim());
		// 0행: R
		// 1행: G
		// 2행: B
		dp = new int[3][N]; 
		
		// 초기 세팅
		st = new StringTokenizer(br.readLine().trim());
		dp[0][0] = Integer.parseInt(st.nextToken());
		dp[1][0] = Integer.parseInt(st.nextToken());
		dp[2][0] = Integer.parseInt(st.nextToken());
		
		for(int idx = 1; idx<N;++idx) {
			st = new StringTokenizer(br.readLine().trim());
			int redCost = Integer.parseInt(st.nextToken());
			int blueCost = Integer.parseInt(st.nextToken());
			int greenCost = Integer.parseInt(st.nextToken());
			
			dp[0][idx] = Math.min(dp[1][idx-1], dp[2][idx-1]) + redCost;
			dp[1][idx] = Math.min(dp[0][idx-1], dp[2][idx-1]) + blueCost;
			dp[2][idx] = Math.min(dp[0][idx-1], dp[1][idx-1]) + greenCost;
		}
		int ans = dp[0][N-1];
		for(int idx = 1; idx<3; ++idx) {
			ans = Math.min(ans, dp[idx][N-1]);
		}
		System.out.println(ans);
	}
}

---

3. 디버깅

최적 부분문제 구조(Optimal substructure)를 만족하는 것을 바탕으로, DP 풀이르 ㄹ떠올려 수월하게 풀 수 있었다.

---

4. 결과