[백준]동적 계획법1/RGB 거리/1149 풀이 JAVA

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

 

풀이(JAVA)

페인트를 칠하는 비용(cost)의 값이 아래와 같다고 하면,

(ex)cost[2][1] = 10; = 3번째 집을 초록색으로 칠하는 데 10의 비용이 듦.

color	0 빨강	1 초록	2 파랑
cost[0][color]	10	20	30
cost[1][color]	30	20	10
cost[2][color]	50	10	30

 

최소 비용의 누적합을 저장하는 dp는 아래와 같다.

(ex)dp[2][1] = 30; = 3번째 집을 초록색으로 칠하는 비용 30 + 2번째 집을 (초록색 제외한 색 중 최소 비용) 파란 색으로 칠하는 비용 10 + 1번째 집을 (파란색 제외한 색 중 최소 비용) 빨간 색으로 칠하는 비용 10

color	0 빨강	1 초록	2 파랑
dp[0][color]	10	20	30
dp[1][color]	50(20 + 30)	30(10 + 20)	20(10 + 10)
dp[2][color]	70(10 + 10 + 50)	30(10 + 10 + 10)	60(10 + 20 + 30)

즉, n번째 집을 빨간 색으로 칠할 때,

dp[n][0] = Math.min(dp[n - 1][1], dp[n - 1][2]) + cost[n][color];라는 점화식을 세울 수 있다.

(n번째 집을 빨간 색으로 칠할 때, 1번째 집부터 n번째 집까지의 최솟값 비용의 누적합 =

빨간색이 아닌 색들 중의 최소 비용 + n번째 집을 빨간색으로 칠한 비용)

 

	import java.io.*;
	import java.util.StringTokenizer;
	public class Main {
	static int[][] cost; // 페인트 비용을 입력받을 배열
	// ex) cost[n][i] = 100; = (n + 1)번째 집을 i색으로 칠하는 값이 100이다. (i = 0 : 빨, 1 : 초, 2 : 파)
	static int[][] dp; // 누적 합계를 저장할 배열
	// ex) dp[3][1] = 200; = 4번째 집을 초록색으로 칠할 때, 1번째 집부터 4번째 집까지 색이 겹치지 않는 최솟값 비용의 누적합이 200이다.
	// 최솟값 누적 구하기
	static int find(int N, int color) {
	if (dp[N][color] == 0) { // n번째 집을 color색으로 칠할 때(1번째 집부터 n번째 집까지 칠할 때의 최솟값 비용의 누적합을 구하지 못했을 때)
	// n번째 집을 빨간 색으로 칠할 때, 1번째 집부터 n번째 집까지의 최솟값 비용의 누적합 =
	if (color == 0) // (n - 1번째 집은 초록색과 파란색이어야함.) 둘 중 최솟값 + n번째 집을 빨간 색으로 칠하는 비용
	dp[N][0] = Math.min(find(N - 1, 1), find(N - 1, 2)) + cost[N][0];
	// n번째 집을 초록 색으로 칠할 때, 1번째 집부터 n번째 집까지의 최솟값 비용의 누적합 =
	else if (color == 1) // (n - 1번째 집은 빨강색과 파란색이어야함.) 둘 중 최솟값 + n번째 집을 초록 색으로 칠하는 비용
	dp[N][1] = Math.min(find(N - 1, 0), find(N - 1, 2)) + cost[N][1];
	// n번째 집을 파란 색으로 칠할 때, 1번째 집부터 n번째 집까지의 최솟값 비용의 누적합 =
	else // (n - 1번째 집은 빨강색과 초록색이어야함.) 둘 중 최솟값 + n번째 집을 파란 색으로 칠하는 비용
	dp[N][2] = Math.min(find(N - 1, 0), find(N - 1, 1)) + cost[N][2];
	}
	// 1번째 집부터 n번째 집을 color색으로 칠할 때까지의 최솟값 비용의 누적합을 모두 구하면 반환
	return dp[N][color];
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	// 집의 수 입력
	int N = Integer.parseInt(br.readLine());
	cost = new int[N][3]; // 페인트 비용을 입력받을 배열 생성
	dp = new int[N][3]; // 누적 합계를 저장할 배열 셍성
	// 페인트 비용 입력
	for (int n = 0; n < N; n++) {
	st = new StringTokenizer(br.readLine());
	for (int i = 0; i < 3; i++) // cost 배열에 비용 저장
	cost[n][i] = Integer.parseInt(st.nextToken());
	}
	// 첫 번째 집을
	dp[0][0] = cost[0][0]; // 빨간 색으로
	dp[0][1] = cost[0][1]; // 초록 색으로
	dp[0][2] = cost[0][2]; // 파란 새긍로 칠할 때의 비용 저장
	int red = find(N - 1, 0); // 마지막 집을 빨간 색으로 칠할 때의 최솟값 비용의 누적합
	int green = find(N - 1, 1);// 마지막 집을 초록 색으로 칠할 때의 최솟값 비용의 누적합
	int blue = find(N - 1, 2); // 마지막 집을 파란 색으로 칠할 때의 최솟값 비용의 누적합
	// 위의 셋 중 최솟값 구해서 출력
	System.out.println(Math.min(Math.min(red, green), blue));
	}
	}

view raw 1149.java hosted with ❤ by GitHub

---

이해하기 어렵다고 생각했는데 알고보니... 그렇게 어렵진 않았다.

그냥 엄청 꼬아꼬아 생각한 듯... 넓게 보자.