[Java] 백준 1149.RGB거리

➡️문제 링크

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

 

 

 

💡아이디어

최솟값을 보고 BFS를 떠올렸다

그러다 첫 번째 집부터, R, G, B 세가지 선택지가 있고

앞에서 어떤걸 선택하냐에 따라 앞으로의 선택도 계속 달라지는데 BFS만으로 되나? 싶었고

혹시 DP인가 싶다가 설마~ 이런생각으로 완탐으로 접근했다

 

 

✏️문제 풀이

1. 완전 탐색 - 오답(시간초과)

이전에 선택한 색을 제외한 나머지 색을 고르면 계속 N번째까지 도는 방법으로 구현했다.

문제에서 주어진 예제는 다 맞혔지만, 시간초과가 발생했다.

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int [][] cost;
	static int [] color;
	static int count = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cost = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 완탐
		for(int i = 0; i < 3; i++) {
			init();
//			color[0] = i;
			dfs(1, i, cost[0][i]);	// 그 다음 집 번호,이전에 선택한 색깔, 누적값
		}
		
		// 정답
		System.out.println(count);
		
	}
	
	static void dfs(int curIdx, int preColor, int sum) {
		if(curIdx == N) {
			count = Math.min(count, sum);
			return;
		}
		
		for(int i = 0; i < 3; i++) {	// r, g, b 다름
			if(i == preColor) continue;	// 이전 집에서 택한 색하고는 다륵
			
			dfs(curIdx+1, i, sum+cost[curIdx][i]);
		}
	}
	
	
	static void init() {
		color = new int[N];
		Arrays.fill(color, -1);
	}
	
	
}

 

 

2. DP - 성공

설마가 맞았다

알고리즘 유형 힌트를 보니 DP가 맞았다

그렇다면 DP의 꽃, 점화식을 정의해야한다.

처음에는 집이 N개 나란히 있으니 1차원 배열을 떠올렸지만,

그렇게 된다면 dp[i]가 최선의 선택을 의미할 수 있을가? 지금은 R을 선택했지만, 뒤에서보니 G를 선택하는게 더 나은 방법일수도 있는데!

그래서 2차원 배열이라고 가정하고, dp[i][j]의 의미를 생각해봤다.

i번째 집의 컬러를 j로 선택했을 때, 그때까지 최솟값

이거다! 싶어서 바로 들어갔다

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int [][] cost;
	static int [] color;
	static int count = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cost = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// DP
		int [][] dp = new int[N][3];	// dp[i][j]: i번째 집의 색을 j롤 선택했을 때 최솟값
		dp[0][0] = cost[0][0];
		dp[0][1] = cost[0][1];
		dp[0][2] = cost[0][2];
		
		for(int i = 1; i < N; i++) {
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2])+cost[i][0];
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2])+cost[i][1];
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1])+cost[i][2];
		}
		
		// 정답
		System.out.println(Math.min(Math.min(dp[N-1][0], dp[N-1][1]), dp[N-1][2]));
		
	}
	
}

 

 

 

 

이 문제의 어느 부분에서 DP임을 알아채야했을까 생각해봤는데

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

이 부분이 아닐까 싶다

처음에는 읽으면서

"그냥 이전값하고 현재값하고 다르게 선택하라는 거 아닌가? 한 줄만 써도 되는데 왜 굳이 세 줄이나 줬지?"싶었는데..

DP임을 알고 다시 읽어보니 그냥 "나 DP라고!!!!" 소리쳐주는 것 같았다

이전 선택이 다음에 영향을 준다

잊지 않겠어