[백준_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번 집의 색과 같지 않아야 한다.

 

[입력 조건]

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

 

[코드]

import java.util.Scanner;

public class BaekJoon_1149 {
	static int[][] cost; // 입력받은 비용을 저장하는 함수
	static Integer[][] dp; // 탐색하면서 누적합을 저장할 함수
	static final int Red=0,Green=1,Blue=2;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		cost=new int[n][3];
		dp=new Integer[n][3];
		
		for(int i=0;i<n;i++) {
			cost[i][Red]=sc.nextInt(); 
			cost[i][Green]=sc.nextInt();
			cost[i][Blue]=sc.nextInt();
		}
		
		// 첫 번째 값은 각 색상 비용의 첫 번쨰 값으로 초기화
		dp[0][Red]=cost[0][0];
		dp[0][Green]=cost[0][1];
		dp[0][Blue]=cost[0][2];
		
		System.out.println(Math.min(paint_house(n- 1, Red), Math.min(paint_house(n - 1, Green), paint_house(n - 1, Blue))));
	}
	
	/*
	 * dp[n][color]에는 각 n에 대해 빨/파/초로 색칠했을 때 가장 작은 값이 저장되어 있다.
	 * 이때 dp[n][color]의 값을 구하기 위해서는 해당 색을 제외한 나머지 두 색 중에 비용이 더 적은 값에 해당 색을 더해주면 된다. 
	 * 이때 나머지 색들 중 비용이 더 적은 값을 구하기 위해서는 이전 집들을 색칠해 해당 n까지 도달한 값을 더해줘야 하기 때문에 재귀 호출을 사용하여 구해준다.
	 */
	public static int paint_house(int n, int color) {
		//해당 배열의 값을 탐색하지 않았다면 color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
		if(dp[n][color]==null) {
			if(color==Red) 
				dp[n][Red]=Math.min(paint_house(n-1,Blue), paint_house(n-1,Green))+cost[n][Red];
			else if(color==Green) 
				dp[n][Green]=Math.min(paint_house(n-1,Blue), paint_house(n-1,Red))+cost[n][Green];
			else 
				dp[n][Blue]=Math.min(paint_house(n-1,Red), paint_house(n-1,Green))+cost[n][Blue];
		}
		return dp[n][color];
	}
}

 

[고찰]

 이번 문제는 앞선 동적 계획법 보다는 어려운 문제였다. dp[n][color] 값을 어떻게 갱신시켜주냐가 가장 중요한 포인트였는데 n 직전까지의 해당 color 이외의 두 색 중에 누적된 비용이 더 적은 값과 해당 색을 사용하였을 때의 비용을 더하는 방식으로 계산해주어야 한다.이 부분을 이해하고, 구현하는데 시간이 좀 걸렸다.