[백준] 1149번 RGB거리 자바

문제 (DP)

 

1149번: RGB거리

 

 

문제 풀이

 

처음에 DFS로 모든 경우에 한해 값을 계산하고 최소값을 갱신하는 방법으로 풀었는데 시간초과가 떴다.

구글링해보니 dp로 생각보다 간단하게 풀 수 있었다. 

행렬의 크기를 [N][3]으로 잡아서 행은 집의 개수, 열은 RGB를 나타내는 개수로 각 집의 색상을 어떤 것을 칠하느냐에 따라 dp배열을 갱신한다. 모든 칠하는 경우의 개수를 보게 되므로 그 전 집의 색깔 중에서 최소값을 바로 택해도 가능하다.

 

 

소스 코드

 

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

public class b_1149 {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] cost = new int[N][3];
		int[][] dp = new int[N][3];
		
		//cost입력 받기
		for(int i = 0; i < N; i++) {
			String[] str = br.readLine().split(" ");
			for(int j = 0; j < 3; j++)
				cost[i][j] = Integer.parseInt(str[j]);
		}
		
		//dp생성
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 3; j++) {
				if(i == 0)
					dp[i][j] = cost[i][j];
				else {
					if(j == 0)	//r칠하는 경우
						dp[i][j] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][j];
					else if(j == 1)	//g칠하는 경우
						dp[i][j] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][j];
					else if(j == 2)	//b칠하는 경우
						dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][j];
				}
			}
		}
		
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < 3; i++) {
			if(dp[N-1][i] < min)
				min = dp[N-1][i];
		}
		
		System.out.println(min);
	}
	
}