[백준, BOJ 17404] RGB거리 2 (java)

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

17404번: RGB거리 2

---

문제

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

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

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

입력

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

출력

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

728x90

 

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

110

 

예제 입력 2

3
1 100 100
100 1 100
100 100 1

예제 출력 2

3

 

예제 입력 3

3
1 100 100
100 100 100
1 100 100

예제 출력 3

201

 

예제 입력 4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4

208

 

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

253

---

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

public class Main {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int[][][] dp = new int[N - 1][3][3];
		
		// 초기값
		st = new StringTokenizer(br.readLine());
		int r1 = Integer.parseInt(st.nextToken());
		int g1 = Integer.parseInt(st.nextToken());
		int b1 = Integer.parseInt(st.nextToken());
		
		// 초기값 세팅
		st = new StringTokenizer(br.readLine());
		int r2 = Integer.parseInt(st.nextToken());
		int g2 = Integer.parseInt(st.nextToken());
		int b2 = Integer.parseInt(st.nextToken());
		dp[0][0][1] = g1 + r2;
		dp[0][0][2] = b1 + r2;
		dp[0][1][0] = r1 + g2;
		dp[0][1][2] = b1 + g2;
		dp[0][2][0] = r1 + b2;
		dp[0][2][1] = g1 + b2;
		
		// 다음 값들
		for (int i = 1; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int[] now = new int[3];
			for (int j = 0; j < 3; j++) {
				now[j] = Integer.parseInt(st.nextToken());
			}
			
			// R
			for (int j = 0; j < 3; j++) {
				if(dp[i - 1][1][j] == 0) dp[i][0][j] = dp[i - 1][2][j] + now[0];
				else if(dp[i - 1][2][j] == 0) dp[i][0][j] = dp[i - 1][1][j] + now[0];
				else dp[i][0][j] = Math.min(dp[i - 1][1][j], dp[i - 1][2][j]) + now[0];
			}
			
			// G
			for (int j = 0; j < 3; j++) {
				if(dp[i - 1][0][j] == 0) dp[i][1][j] = dp[i - 1][2][j] + now[1];
				else if(dp[i - 1][2][j] == 0) dp[i][1][j] = dp[i - 1][0][j] + now[1];
				else dp[i][1][j] = Math.min(dp[i - 1][0][j], dp[i - 1][2][j]) + now[1];
			}
			
			// B
			for (int j = 0; j < 3; j++) {
				if(dp[i - 1][0][j] == 0) dp[i][2][j] = dp[i - 1][1][j] + now[2];
				else if(dp[i - 1][1][j] == 0) dp[i][2][j] = dp[i - 1][0][j] + now[2];
				else dp[i][2][j] = Math.min(dp[i - 1][0][j], dp[i - 1][1][j]) + now[2];
			}
		}
		
		// 마지막 값은 첫 번째 값이랑 같으면 안됨
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if(i == j) continue;
				result = Math.min(dp[N - 2][i][j], result);
			}
		}
		
		System.out.println(result);
	}

}