[백준] 1149번: RGB거리(DP)

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

1149번: RGB거리

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		int[][] dp = new int[N][3];
		int minMoney = 0;
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			dp[i][0] = Integer.parseInt(st.nextToken());	// Red
			dp[i][1] = Integer.parseInt(st.nextToken());	// Green
			dp[i][2] = Integer.parseInt(st.nextToken());	// Blue
		}
		
		for(int i=1; i<N; i++) {
			dp[i][0] += Math.min(dp[i-1][1], dp[i-1][2]);	// R일때 최소 비용 -> G, B 비교
			dp[i][1] += Math.min(dp[i-1][0], dp[i-1][2]);	// G일때 최소 비용 -> R, B 비교
			dp[i][2] += Math.min(dp[i-1][0], dp[i-1][1]);	// B일때 최소 비용 -> R, G 비교
		}
		minMoney = Math.min(dp[N-1][0], (Math.min(dp[N-1][1], dp[N-1][2])));	// R, G, B 중 최소 비용 구하기
		System.out.println(minMoney);
		bf.close();
	}

}

풀이

전형적인 Dynamic Programming(동적 계획법)의 문제다. 아직은 DP문제에 대한 감이 좀 부족한 상태여서 블로그들을 참고하니 2차원배열로 해결하길래, 참조해서 풀어보니 해결할 수 있었다.

i번째 집에 색을 칠할때, 그 i번째의 집에 R, G, B 세 가지의 색을 칠하는 경우의 수를 살펴봐야한다.

 

● i번째에 빨강색을 칠할 경우.

  i-1번째에 칠할 수 있는 색은 초록색과 파랑색이 있다.

따라서 i번째에 칠할 수 있는 최소 비용은 ...

초록 + 빨강 = dp[i][1] + dp[i][0]

파랑 + 빨강 = dp[i][2] + dp[i][0] 

두 개의 값 중 최솟값이 최소 비용이 된다.

 

위 식을 점화식으로 세우면 다음과 같다.

dp[i][0] += Math.min(dp[i-1][1], dp[i-1][2]);

-> i번째 집을 빨강색으로 칠할 경우 -> i-1번째가 초록과 파랑중 최솟값의 경우이다.

 

마찬가지로 초록, 파랑색의 경우도 동일한 점화식을 세울 수 있다.

dp[i][1] += Math.min(dp[i-1][0], dp[i-1][2]);
dp[i][2] += Math.min(dp[i-1][0], dp[i-1][1]);	

따라서 dp[i][] 번째에는,

dp[i][0] => i번째를 빨강색으로 칠할 경우의 최소 비용

dp[i][1] => i번째를 초록색으로 칠할 경우의 최소 비용

dp[i][2] => i번째를 파랑색으로 칠할 경우의 최소 비용

이 저장된다.

세 값중 가장적은 최소비용을 선택하면 그 값이 결과값이 된다.

 

 

 

Scanner(아래) 와 BufferedReader(위)의 시간 차이, 약 2배 !

 

 

더 상세한 해설을 원하면 아래를 클릭,

백준1149번