[JAVA] BOJ(백준) - RGB거리 - 1149

문제 내용

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

출력

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

 

---

문제 접근 방법

처음 문제를 보고 이건 백트래킹 방식으로 풀어야 하나..? 생각을 했는데 풀수는 있을것 같지만 뭔가 시간초과나고 삽질할꺼 같은 느낌이 들어서 그냥 DP 방식으로 풀기로 했다.

 

그러기 위해 먼저 규칙을 찾아 식을 세워야하는데 이부분이 진짜 가장 어려웠던 문제다.

 

먼저 집 a b c d e f  가 순서대로 있다고 했을때 집 c는 b,d와는 다른 색이여야하고 집 d는 c,e와 다른 색을 갖고 있어야한다. 즉, 인접해 있는 집들은 같은색이 있을 수 없다.

그리고 이문제는 집을 색칠하면서 비용을 누적하고 RGB 경우에 따라 누적된 비용의 최솟값을 찾는 문제다.

 

그러면 비용을 누적하기 위해선 주어진 입력값(비용)을 활용하면 된다.

예를들어, 집 N을 R의 색으로 색칠 한다면

N-1(전에 있는집)이 G색이나 ,B색으로 칠해져야 한다. 이때 G와 B를 칠하는 비용중 최소비용을 선택하여 N 까지 누적시키면 집(N)이 R색일때 최소비용이 된다.

 

정리하면!

집 N을 R색으로 칠할때 누적된 최소 비용을 (N,R) 이라고 하고 입력받은 비용을 cost 라 할떄, 식을 세워보면

(N, R) = ( (N-1, G) 와 (N-1, B) 중 최소비용) +  cost(N, R) 이라 할수 있다.

그러면 DP 배열은 dp[집][색] 으로 표현 할 수 있고,

최종 출력값은 dp[집][R], dp[집][G], dp[집][B] 중 최소 값을 선택하면 답이다.

 

잘 이해가 안될수도 있는데 풀이를 보고 생각해보자.

 

---

풀이

재귀(TopDown)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
 * RGB거리
 * 백준 - DP
 * 
 * f[1][0] = Math.min(f[0][1],f[0][2]) + 현비용[1][0]
 * 			...
 * f[n][0] = Math.min(f[n-1][1]+f[n-1][2]) + 현비용[n][0]
 *
 */
public class BOJ_1149_1 {
	static int[][] cost; //입력받은 비용
	static int[][] dp; //색에 따라 비용을 누적시킬 DP 배열
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine()); //집 개수
		
		//0번 인덱스는 사용 안함
		cost = new int[N+1][3]; //cost[집][색]
		dp = new int[N+1][3]; //dp[집][색]
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//1번집의 색이 0,1,2 일때 비용 초기화
		dp[1][0] = cost[1][0];
		dp[1][1] = cost[1][1];
		dp[1][2] = cost[1][2];
		
		//마지막 집까지 색을 다칠했을때 경우의 수 3가지
		int R = minCost(N,0); //마지막집이 R로 칠해진 경우
		int G = minCost(N,1); //마지막집이 G로 칠해진 경우
		int B = minCost(N,2); //마지막집이 B로 칠해진 경우
		int min = Math.min(R, Math.min(G,B));
		System.out.println(min);
	
	}
	
	//모든 경우의수를 생각할 필요없음.
	//매번 집을 칠할떄마다 전에 있는집과 색은 다르게하고 다른 색중에 최소비용이 드는 색으로만
	//칠해주면 됨.
	public static int minCost(int n, int color){
		if(dp[n][color]!=0) {//이미 칠해진경우
			return dp[n][color];
		}
		if(color==0) {
			dp[n][color] = Math.min(minCost(n-1,1), minCost(n-1,2)) + cost[n][color]; 
		}else if(color==1) {
			dp[n][color] = Math.min(minCost(n-1,0), minCost(n-1,2)) + cost[n][color];
		}else {
			dp[n][color] = Math.min(minCost(n-1,0),minCost(n-1,1)) + cost[n][color];
		}
		
		return dp[n][color];
	}
}

 

---

마무리

이번 문제는 입력받은 cost배열을 활용해 어떤 기준으로 dp배열을 만들지,

어떤 규칙을 찾아내서 식을 세우는지가 개인적으로는 어려웠던 문제이다...후..