백준 17404번: RGB거리 2

문제 설명

• https://www.acmicpc.net/problem/17404
• 각 행마다 R,G,B 중 하나의 값을 선택해 최소값을 만들어야 합니다.이 때 인접한 칸과 동일한 색으로 색칠할 수 없으며 시작과 끝이 이어진 원형 모양입니다.

접근법

• RGB거리 1를 먼저 풀어보는 걸 권장합니다.

  • 위 문제와 지금 문제는 처음과 끝이 인접해 있다는 차이밖에 없습니다.

• 해당 문제는 N번째 값을 선택할 때 지금까지 만든 최솟값의 출발이 어디였는지에 대한 정보가 필요합니다. 처음에는 출발값을 담은 객체를 만들어 문제를 해결하려 했지만 풀리지 않았습니다.

  • 시작이 R인 경우, G인 경우, B인 경우를 각각 실행하고, 마지막 값을 제한하면 됩니다. 단순하게 모든 경우의 수는 R 또는 G 또는 B로 시작한다는 걸 생각하면 조금 더 쉽게 접근할 수 있습니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] board = new int[N][3];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		int minVal = Integer.MAX_VALUE;
		for (int t = 0; t < 3; t++) {			
			int[][] dp = new int[N][3];
			for (int k = 0; k < 3; k++) {
				if(k == t) {
					dp[0][k] = board[0][k];
				}else {
					dp[0][k] = 1001;
				}
			}
			for (int i = 1; i < N-1; i++) {
				dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + board[i][0];
				dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + board[i][1];
				dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + board[i][2];
			}
			// 마지막 값 처리
			if(t == 0) {
				dp[N-1][0] = Integer.MAX_VALUE;
				dp[N-1][1] = Math.min(dp[N-2][0], dp[N-2][2]) + board[N-1][1];
				dp[N-1][2] = Math.min(dp[N-2][0], dp[N-2][1]) + board[N-1][2];
			}else if (t == 1){
				dp[N-1][1] = Integer.MAX_VALUE;
				dp[N-1][0] = Math.min(dp[N-2][1], dp[N-2][2]) + board[N-1][0];
				dp[N-1][2] = Math.min(dp[N-2][0], dp[N-2][1]) + board[N-1][2];
			}else if(t == 2) {
				dp[N-1][2] = Integer.MAX_VALUE;
				dp[N-1][0] = Math.min(dp[N-2][1], dp[N-2][2]) + board[N-1][0];
				dp[N-1][1] = Math.min(dp[N-2][0], dp[N-2][2]) + board[N-1][1];				
			}
			
			int answer = Math.min(Math.min(dp[N-1][0], dp[N-1][1]),dp[N-1][2]);
//			for (int i = 0; i < dp.length; i++) {
//				System.out.println(Arrays.toString(dp[i]));
//			}
			minVal = Math.min(minVal, answer);
		}
		System.out.println(minVal);
		
	}
}