[BOJ] 1149 RGB거리 (Java)

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

알고리즘

DP

풀이

1. 마지막 집이 Red로 칠해진 경우, 이전 집이 Green, Blue로 칠해진 경우 중 최적값과 마지막 집의 red값을 더한 값으로 저장한다.
2. 마지막 집이 Green로 칠해진 경우, 이전 집이 Red, Blue로 칠해진 경우 중 최적값과 마지막 집의 red값을 더한 값으로 저장한다.
3. 마지막 집이 Blue로 칠해진 경우, 이전 집이 Green, Red로 칠해진 경우 중 최적값과 마지막 집의 red값을 더한 값으로 저장한다.
4. 마지막 집이 red, blue, green으로 칠해진 최적값 중 최소값을 구한다.

코드

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

public class Main_1149_RGB거리 {

	static int N;
	static int[][] RGB, DP;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		RGB = new int[N][3];											// 각 집마다 RGB로 칠하는 비용을 저장할 배열 
		DP = new int[N][3];												// 각 집이 Red, Green, Blue로 색칠될 때, 최소값을 저장할 배열 
		
		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());			// 각 집마다의 RGB 비용 입력 
				if(i==0) DP[i][j] = RGB[i][j];							// 첫번째 집의 경우 최소값 = 첫번쨰 집을 RGB로 칠하는 비용 
			}
		}
		
		for(int i=1; i<N; i++) {										// 두번째 집부터 마지막 집까지 반복 
			DP[i][0] = Math.min(DP[i-1][1], DP[i-1][2]) + RGB[i][0]; 	// i번째 집이 R로 칠해질 경우, i-1번째 집이 G, B 로 칠해진 경우 중 최저 비용에 R로 칠할 때의 비용을 더해줌  
			DP[i][1] = Math.min(DP[i-1][0], DP[i-1][2]) + RGB[i][1]; 	// i번째 집이 G로 칠해질 경우, i-1번째 집이 R, B 로 칠해진 경우 중 최저 비용에 G로 칠할 때의 비용을 더해줌  
			DP[i][2] = Math.min(DP[i-1][0], DP[i-1][1]) + RGB[i][2]; 	// i번째 집이 B로 칠해질 경우, i-1번째 집이 R, G 로 칠해진 경우 중 최저 비용에 B로 칠할 때의 비용을 더해줌  
		}
		
		Arrays.sort(DP[N-1]);											// 마지막 집이 RGB로 칠해진 결과를 정렬 
		System.out.println(DP[N-1][0]);									// 0번째 값 출력(가장 작은값 )
		br.close();
	}
}