[백준/JAVA] 1149: RGB거리

[백준/JAVA] 1149: RGB거리

연속된 주어진 집들을 R, G, B 색상으로 칠해야 하는데, 이때 이웃하는 집끼리는 같은 색이 될 수 없다. 집을 칠하는 비용은 각각의 색상에 따라 달라지며, 조건에 따라 색을 칠할 때 비용이 최소가 되도록 한다.

처음 1번째 집을 어느 색상으로 정하느냐에 따라 경로가 달라진다.

1. i번째 집을 R로 칠하는 최소비용은 i-1번째 집이 G 또는 B로 칠해져 있을 때의 최소 비용을 선택하면 된다.

2. i번째 집을 G로 칠하는 최소비용은 i-1번째 집이 R 또는 B로 칠해져 있을 때의 최소 비용을 선택하면 된다

3. i번째 집을 B로 칠하는 최소비용은 i-1번째 집이 G 또는 R로 칠해져 있을 때의 최소 비용을 선택하면 된다.

DP는 다음 값을 구할 때 이전 값이 이미 구해져 있어 다음 값을 빠르게 구할 수 있는 방법(bottom-up)에 기반을 둔다. for문을 돌 때 i번째 집을 칠하는 최소 비용은 i-1번째 집을 i번째 집을 칠한 색이 아닌 나머지 두 가지 색으로 칠한 비용 중 최소인 것에 i번째 집을 칠하는 비용을 더하여 구할 수 있다.

소스코드

---

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

public class Main {
	public static int n;
	public static int arr[][];
	public static int dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        arr = new int[n][3];
        for (int i=0; i<n; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	for (int j=0; j<3; j++)
        		arr[i][j] = Integer.parseInt(st.nextToken());
        }
        
        dp = new int[n][3];
        System.out.println(findMin());
    }
    
    // 서로 이웃한 집끼리는 색이 같지 않아야 한다.
    public static int findMin() {
    	for(int i=0; i<3; i++)
    		dp[0][i] = arr[0][i];
    	/* dp[x][0] : x번째 집을 R로 칠하는 최소비용
    	 * dp[x][1] : x번째 집을 G로 칠하는 최소비용
    	 * dp[x][2] : x번째 집을 B로 칠하는 최소비용
    	 */
    	
    	for (int i = 1; i < n; i++) {
            dp[i][0] = arr[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = arr[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = arr[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
        }
    	return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }
}