[백준 1149] RGB거리

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

DP문제입니다

2차원 배열을 사용했습니다.

맨 마지막줄(N)까지의 최소값을 구하기 위해 이 값을 D[N]이라 하고, 현재 N번째 줄의 값을 P[N] 이라 한다면

D[N] = D[N-1] + P[N]이 되겠죠.

최소값을 구할때는 현재 해당하는 집의 RGB 구할때는

앞집의 색깔 중 현재 집의 색깔을 제외한 나머지 부분을 확인해주시면 됩니다

이 식을 적용해 풀면 됩니다.

 

public class Q1149 {
	static int[][] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int num = Integer.parseInt(br.readLine());
		arr = new int[num+1][3];
		
		int minV;
		for(int i=1; i<arr.length; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][2] = Integer.parseInt(st.nextToken());
			
			arr[i][0] += Math.min(arr[i-1][1], arr[i-1][2]);
			arr[i][1] += Math.min(arr[i-1][0], arr[i-1][2]);
			arr[i][2] += Math.min(arr[i-1][0], arr[i-1][1]);
		}
		minV = Math.min(Math.min(arr[num][0], arr[num][1]), arr[num][2]);
		System.out.println(minV);
	}
}