[백준] 1149번 RGB 거리 (자바 풀이)

문제

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

1149번: RGB거리

 

풀이

처음에는 단순 DFS로 문제를 접근했다. 하지만 DFS를 사용하면 시간 초과가 발생한다. 

이 문제는 DP를 사용해서 해결해야 한다. 점화식을 아래와 같이 세우면 된다.

 

dp[i][j] = i번째 집을 j 색깔로 칠할 때 비용의 최솟값

dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) // 이때 j와 같은 숫자는 제외 -> 같은 색깔 제외

생각보다 간단한 문제였다.

 

코드

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

public class Baekjoon_1149 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int color[][] = new int[N+1][3];
		int dp[][] = new int[N+1][3];
		int ans = Integer.MAX_VALUE;
		
		for(int i=1; i<=N; i++) {
			color[i][0] = sc.nextInt();
			color[i][1] = sc.nextInt();
			color[i][2] = sc.nextInt();
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=0; j<3; j++) {
				int min = Integer.MAX_VALUE;
				for(int k=0; k<3; k++) {
					if(j==k) continue; 	// 같은 색 
					min = Math.min(min, dp[i-1][k]);
				}
				dp[i][j] = min + color[i][j];
			}
		}
		
		for(int i=0; i<3; i++) {
			ans = Math.min(ans, dp[N][i]);
		}
		System.out.println(ans);
	}
}