[boj] RGB거리 2_17404 JAVA

문제는 다음과 같다핑

 

문제에 대하여 간략히 설명을 해보자면,

 

1. 각 집은 빨강, 초록, 파랑 중 하나로 칠해야 한다.

2. 옆집과 같은 색으로 칠할 수 없다.

3. 첫 번째 집과 마지막 집도 서로 다른 색이어야 한다.

 

의 조건을 만족하는, 색 최소비용을 더해서 구하면 된다.

 

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


public class RGB거리2_17404 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[][] arr = new int[n + 1][3], dp = new int[n + 1][3];
        StringTokenizer st = null;

        for(int i = 1 ; i <= n; i++){
            st = new StringTokenizer(bf.readLine());
            for(int j = 0 ; j < 3; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = 10000001;
        for(int k = 0; k < 3; k++) {
            for(int i = 0 ; i < 3; i++) {
                if(i == k) {
                    dp[1][i] = arr[1][i];
                }
                else {
                    dp[1][i] = ans;
                }
            }

            for (int i = 2; i <= n; i++) {
                dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
            }
            
            for(int i = 0 ; i < 3; i++) {
                if(i != k) {
                    ans = Math.min(ans, dp[n][i]);
                }
            }
        }
        System.out.println(ans);
    }
}

 

전형적인 dp 문제!

먼저 arr 배열로 색 별 가격을 쭉 받은다음, dp 배열로 집을 빨강, 초록, 파랑으로 칠하는 세 가지 경우를 각각 고려한다.

그 후 dp 배열을 만들어 dp[i][j]를 i번째 집을 색깔 j로 칠할 때의 최소 비용으로 둔다.

dp[i][j] = min(dp[i-1][k]) + arr[i][j]

 

마지막 집은 첫 번째 집과 같은 색이 될 수 없으므로, 첫 번째 집의 색깔과 다른 색깔 중 최소 비용을 선택한다.

                if(i != k) {
                    ans = Math.min(ans, dp[n][i]);
                }