백준 1149 - RGB거리 JAVA

문제 / 입출력조건

테스트케이스

해당 문제 접근과정

1. 집이 3개인 경우로 일단 집 선택하는 경우의 수 나열 -> 실패

2. 각 집 방문할 경우에서 가장 작은 값 선택(그리디, dfs) -> 실패 (시간 터짐)

3. 2번에서 dp로다가 점화식인 f(특정 컬러를 선택하였을 때 N번 째 집의 도색 비용) = 특정 컬러로 N번 째 집의 도색 비용 + min(f(n번째 집에서 선택하지 않은 색을 선택하였을 때 N-1번 째 집의 도색 비용)) 도출

4. 구현에서 애먹음

5. 구선생님의 도움을 받음

 

아래와 같이 단계별 문제 풀기에서 DP를 풀며 느끼는 것은 점화식을 구하는 것도 구하는 것이지만 그걸 어떻게 구현하지? 가 더 큰 문제로 보인다. 내 머리의 공간지각 능력? 상상력을 키워야 할 때가 온 것 같다...

 

package boj;

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

public class Boj_1149 {
	static int colorCost[][];
	static int dp[][];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// 매순간 그리디하게 선택한다고 생각해본다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		colorCost = new int[N][3];
		dp = new int[N][3];
		StringTokenizer stz;
		for (int i = 0; i < N; i++) {
			stz = new StringTokenizer(br.readLine());
			if (i == 0) {
				dp[i][0] = Integer.parseInt(stz.nextToken());
				dp[i][1] = Integer.parseInt(stz.nextToken());
				dp[i][2] = Integer.parseInt(stz.nextToken());
				colorCost[i][0] = dp[i][0];
				colorCost[i][1] = dp[i][1];
				colorCost[i][2] = dp[i][2];
				continue;
			}
			colorCost[i][0] = Integer.parseInt(stz.nextToken());
			colorCost[i][1] = Integer.parseInt(stz.nextToken());
			colorCost[i][2] = Integer.parseInt(stz.nextToken());
		}
		System.out.println(Math.min(findMin(N - 1, 0), Math.min(findMin(N - 1, 1), findMin(N - 1, 2))));
	}

	static int findMin(int homeN, int color) {

		if (dp[homeN][color] == 0) {
			switch (color) {
			case 0:
				dp[homeN][color] =colorCost[homeN][color] + Math.min(findMin(homeN - 1, 1), findMin(homeN - 1, 2));
				break;
			case 1:
				dp[homeN][color] = colorCost[homeN][color] +  Math.min(findMin(homeN - 1, 0), findMin(homeN - 1, 2));

				break;
			case 2:
				dp[homeN][color] = colorCost[homeN][color] + Math.min(findMin(homeN - 1, 0), findMin(homeN - 1, 1));
				break;
			}
		}

		return dp[homeN][color];

	}
}