백준 1149번 : RGB 거리 풀이 (Java) - DP

www.acmicpc.net/problem/1149

1149번: RGB거리

한 번 풀어본 문제라서 쉽게 풀었다.

 

Solution

1. 이 문제는 DP 문제이다. N번 집은 N-1 번 집의 색과 같으면 안된다. 세 번째 조건인 

• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

에서 좀 헷갈릴 수 있는데, 어차피 N-1 번의 집과 N번의 집을 다르게 칠한다면, N+1번도 N번과 다르게 칠하므로 상관없다.

2. 그러므로, 집의 개수 N * 칠할 수 있는 색의 종류 수 3 의 크기의 2차원 배열 dp 를 만든다.

3. dp[i][0] 번은 i번째의 집에 0번 색을 칠한다는 의미이고, 0번 색을 칠하는 데 드는 비용은

 i 번째 집에 0번을 칠하는 비용 + i-1번째 집에 1번을 칠하는 비용과 2번을 칠하는 비용중에 작은 비용

 

이다. 

 

DP에서는 쉬운 문제이다.

 

Source Code

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

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, min;
    private static int[][] costs;
    private static int[][] dp;

    private static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        costs = new int[N][3];
        dp = new int[N][3];
        min = Integer.MAX_VALUE;
        for(int i = 0 ; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0 ; j < 3; j++) {
                costs[i][j] = Integer.parseInt(st.nextToken());
                if(i == 0) {
                    dp[0][j] = costs[0][j];
                }
            }
        }
    }

    private static void solve() throws IOException {
        for(int i = 1; i < N; i++) {
            dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
        }
        min = Math.min(Math.min(dp[N-1][0], dp[N-1][1]), dp[N-1][2]);
        System.out.println(min);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}