백준 1149-RGB 거리; Java

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

public class Main {
	static int N;
	static int[][] house;
	
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		int[][] dp=new int[N][3];
		house=new int[N][3];
		String[] str;
		int temp=Integer.MAX_VALUE;
		for(int i=0;i<N;i++) {
			str=br.readLine().split(" ");
			for(int j=0;j<3;j++) {
				house[i][j]=Integer.parseInt(str[j]);
			}
			
			if(i==0) {
				dp[0][0]=house[0][0];
				dp[0][1]=house[0][1];
				dp[0][2]=house[0][2];
			}else {
				for(int j=0;j<3;j++) {
					temp=Math.min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]);
					dp[i][j]=temp+house[i][j];
				}
			}
		}
		int result=Math.min(dp[N-1][0], dp[N-1][1]);
		result=Math.min(result, dp[N-1][2]);
		System.out.println(result);
	}
}

처음엔 dfs 재귀를 해서 풀었더니 시간초과가 나왔다..

그래서 dp로 배열에 저장하면서 풀었다.

 

R, G, B는 각각 0,1,2

dp[i][R] : i번째 집을 R색으로 칠했을 때 0~i번째 집까지의 최소 cost

dp[i][R] <- Math.min(dp[i-1][G]+cost[i][R], dp[i-1][B]+cost[i][R]) 

(i-1번째 집을 G로 칠했을 때/i번째 집을 B으로 칠했을 때) 중 최솟값+i번째 집을 R으로 칠하는 비용

 

정답은 dp[N-1][R, G, B]중 제일 작은 것