[백준/boj] 1149: RGB거리 (Java) / DP

문제

1149번: RGB거리

코드

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

public class Main {
	static int[][] rgb;
	static int[][] dp;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		rgb = new int[N][3];
		dp = new int[N][3];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				rgb[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = Integer.MAX_VALUE;
			}
		}

		dp[0][0] = rgb[0][0];
		dp[0][1] = rgb[0][1];
		dp[0][2] = rgb[0][2];
		for (int i = 1; i < N; i++) { // 1~ N-1 // 집
			for (int j = 0; j < 3; j++) { // 0~ 2 // 지붕 색 // 이전 집의 지붕색
				for (int k = 0; k < 3; k++) {
					if (j != k) {
						dp[i][k] = Math.min(dp[i][k], dp[i - 1][j] + rgb[i][k]);
					}
				}
			}
		}

		int answer = Math.min(dp[N - 1][0], Math.min(dp[N - 1][1], dp[N - 1][2]));
		System.out.println(answer);
	}
}

변수설명

• rgb[n][c] : n번째 c 컬러를 칠했을 때 드는 비용 (0 <= n < N , N번째 집 == n-1)
• dp[n][c] ( 0<= n < N , 0 <= c <= 2) : n 은 n번째 집을 나타내고, c 는 0: Red , 1: Green , 2: Blue 를 나타낸다. n번째 집에 c를 칠했을 때 비용의 최솟값이 담긴다.

풀이

1. dp는 Integer.MAX_VALUE 로 초기화한다. (0 이 담기면 최솟값 갱신이 안되기 때문)

2. 첫번째 집은 자신의 지붕만 고려하면 되기 때문에 dp[0][0]~ dp[0][2] 는 자신의 값으로 초기화한다.

3. 두번째 집부터는 dp[n][0] 의 경우 dp[n-1][1] + rgb[n][0] 과 dp[n-1][2] + rgb[n][0] 중 작은 값을 할당하면 된다.

dp[n][0] : n번 집 지붕을 빨간색으로 칠할 때 드는 최소 비용값
dp[n-1][1] + rgb[n][0] : 이전 집 지붕을 초록색으로 했을때 드는 최소 비용 값 + 지금 지붕을 빨간색으로 칠할 때 드는 비용 값
dp[n-1][2] + rgn[n][0] : 이전 집 지붕을 파란색으로 했을때 드는 최소 비용 값 + 지금 지붕을 빨간색으로 칠할 때 드는 비용 값