[백준] 1149 : RGB거리 (JAVA)

1149번: RGB거리

Solution

dp 문제인데 삽질을 했다... 아래와 같이 간단히 생각하면 금방 점화식을 도출할 수 있다

	R	G	B
house[0]	house[0][0]	house[0][1]	house[0][2]
house[1]	Math.min(house[0][1], house[0][2]) + house[1][0]	Math.min(house[0][0], house[0][2]) + house[1][1]	Math.min(house[0][0], house[0][1]) + house[1][2]
house[2]	Math.min(house[1][1], house[1][2]) + house[2][0]	Math.min(house[1][0], house[1][2]) + house[2][1]	Math.min(house[1][0], house[1][1]) + house[2][2]
...	...	...	...
house[n]	Math.min(house[n-1][1], house[n-1][2]) + house[n][0]	Math.min(house[n-1][0], house[n-1][2]) + house[n][1]	Math.min(house[n-1][0], house[n-1][1]) + house[n][2]

house[n][0] 은 n+1 번째 집을 빨강으로 칠하려고 할 경우 지금까지 드는 비용의 누적이다. 직전 행(n-1)에서 빨간칠을 하지 않았을 경우의 비용들 중에서 최솟값을 골라 가져오기 때문에 주어진 규칙을 충족한다.

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

class Solution
{
	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[][] house=new int[N][3];
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine()," ");
			house[i][0]=Integer.parseInt(st.nextToken());
			house[i][1]=Integer.parseInt(st.nextToken());
			house[i][2]=Integer.parseInt(st.nextToken());
		}
		
		for(int i=1;i<N;i++) {
			house[i][0]+=Math.min(house[i-1][1], house[i-1][2]);
			house[i][1]+=Math.min(house[i-1][0], house[i-1][2]);
			house[i][2]+=Math.min(house[i-1][0], house[i-1][1]);
		}
		int answer=Math.min(house[N-1][0], house[N-1][1]);
		answer=Math.min(answer, house[N-1][2]);

		System.out.print(answer);
	}
}