[백준] 17404 RGB거리 2 - DP JAVA

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

17404번: RGB거리 2

코드설명

DP 문제입니다.

 

DP[N][Color] 은 N번째 집에서 Color 에 따른 최소비용을 의미합니다.

만약 N번째 집을 빨간색으로 칠할것이라면, N-1번째 집의 초록색, 파랑색의 색칠비용과 비교하여 최소값을 갱신시키면됩니다.

문제에서 유의해야할 조건은 

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. 라는 조건입니다.

그렇기에, 처음에 시작점을 빨간색, 초록색, 파란색을 나누어서 실행합니다.

1번 집을 빨간색으로 칠할경우에는 초록색과 파란색으로는 최소값이 나올 수 없도록 최대값으로 설정합니다.

또한, 마지막에 DP[N-1][0~2] 에서 빨간색일 경우에는 아예 최소경우의 수를 구하는경우를 구하지않도록 로직을 설정하여 1번집의 색과 N번 집의 색이 같지 않도록 처리할 수 있습니다.

코드

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

public class Main {
	public static int T, N;
	public static int[][] arr;
	public static int[][] DP;
	public static long answer = Integer.MAX_VALUE;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N][N];
    	DP = new int[N][3];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<3;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int color=0;color<3;color++) {
    		for(int i=0; i<3;i++) {
    			if(color == i) {
    				DP[0][i] = arr[0][i]; 
    			}else {
    				DP[0][i] = 1001;
    			}
    		}
    		
        	for(int i=1; i<N;i++) {
        		DP[i][0] = Math.min(DP[i-1][1], DP[i-1][2]) + arr[i][0];
        		DP[i][1] = Math.min(DP[i-1][0], DP[i-1][2]) + arr[i][1];
        		DP[i][2] = Math.min(DP[i-1][0], DP[i-1][1]) + arr[i][2];
        	}    		
        	
        	for(int i=0;i<3;i++) {
        		if(i != color) {
        			answer = Math.min(answer, DP[N-1][i]);
        		}
        	}
        	
    	}
    	System.out.println(answer);
	}
}