[백준 17404] RGB거리2

문제

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

17404번: RGB거리 2

 

문제 이해

백준의 RGB거리 2 문제입니다. 백준 1149번 RGB거리 문제에서 첫 집과 마지막 집도 이웃이라는 조건이 추가되었습니다. 첫 집부터 마지막 집까지 순차적으로 비용의 최솟값을 갱신하기 위해서 다이나믹 프로그래밍(Dynamic Programming)을 이용했습니다.

 

풀이

 

①

일단 첫 집과 마지막 집이 이웃이라는 조건을 고려하지 않겠습니다. 먼저 i번째 집을 j번째 색으로 칠하는 비용의 최솟값을 dp[i][j]라 하면, i는 문제에서 주어지는 집의 수인 0~n-1까지이고 j는 0(빨강), 1(초록), 2(파랑)의 범위를 가지게 됩니다.

dp[i][0]: i-1번째 집까지 색을 칠한 비용의 최솟값 + i번째 집을 0(빨강)으로 칠하는 비용

dp[i][1]: i-1번째 집까지 색을 칠한 비용의 최솟값 + i번째 집을 1(초록)로 칠하는 비용

dp[i][2]: i-1번째 집까지 색을 칠한 비용의 최솟값 + i번째 집을 2(파랑)로 칠하는 비용

dp[i][0]를 예시로 들면, 이웃하는 집은 같은 색으로 칠할 수 없다는 조건이 있기 때문에 i-1번째 집을 1 또는 2로 칠한 dp[i-1][1]와 dp[i-1][2] 중 더 적은 비용을 최솟값으로 가지게 됩니다.

 

②

0번째 집부터 n-1번째 집까지 순차적으로 값을 갱신시키기 위해 초기값을 설정합니다. dp[0][0], dp[0][1], dp[0][2]는 입력으로 주어지는 0번째 집을 칠하는 비용을 그대로 넣어줄 수 있습니다. 그리고 i는 1~n-1까지 아래와 같은 점화식으로 해결할 수 있습니다.

dp[i][0]: Math.min(dp[i-1][1], dp[i-1][2]) + i번째 집을 0(빨강)으로 칠하는 비용

dp[i][1]: Math.min(dp[i-1][0], dp[i-1][2]) + i번째 집을 1(초록)로 칠하는 비용

dp[i][2]: Math.min(dp[i-1][0], dp[i-1][1]) + i번째 집을 2(파랑)로 칠하는 비용

i번째 집을 0, 1, 2 중 칠하는 비용은 문제의 input을 그대로 사용할 수 있습니다. n-1까지 최소 비용을 갱신시킨 후, 마지막 n-1번째 집을 칠했을 때의 비용 중 가장 작은 값이 문제의 정답이 됩니다. 즉, dp[n-1][0], dp[n-1][1], dp[n-1][2] 중 최솟값이 정답이 됩니다.

 

③

풀이 ②까지 0번째 집(첫 집)과 n-1번째 집(마지막 집)이 이웃이 아니라는 조건이 없는 1149번 RGB거리 문제 풀이였습니다. 조건이 추가된다면, 0번째 집을 0으로 칠하고 최솟값을 갱신하다가 n-1번째 집을 0으로 칠한 비용이 최솟값이 정답이 될 수 있습니다. 이러한 경우, RGB거리 2 문제의 조건에 위배되기 때문에 0번째 집의 색을 고정시켜 해결해야 합니다.

②에서와 같이 dp[0][0], dp[0][1], dp[0][2]를 한번에 초기값 설정을 하지 않아야 합니다. 예를 들어, 0번째 집을 0 색으로 칠한다면, dp[0][0]은 문제의 input값을 이용하여 그대로 사용하고 나머지 dp[0][1], dp[0][2]는 나올 수 없는 최댓값을 넣어줍니다. 저는 여기서 나올 수 없는 최댓값을 1000(하나의 집을 칠하는 최대 비용) * n(집의 수) + 1로 설정하였습니다. 

 

④

정리해보면 RGB거리 문제 풀이에 for문 하나를 추가하여 0번째 집을 0, 1, 2 중 하나의 색으로 고정시키고 나머지는 최댓값을 넣어준 뒤, dp배열을 0~n-1까지 갱신시키고 0번째 집을 0 색으로 칠했으면 dp[n-1][1], dp[n-1][2] 중 작은 값을 정답으로 합니다. 정답은 색을 고정시키는 for문이 끝날 때마다 갱신시켜 0, 1, 2 중 하나의 색으로 고정시키고 계산이 끝난 후 지속적으로 갱신시켜주면 문제에서 원하는 결과값을 얻을 수 있습니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ_17404 {
    static int n, pmax, ans;
    static int[][] a, dp;
    static StringTokenizer str;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n][3]; //a[i][j]: i번째 집을 j번째 색깔로 칠할 때 들어가는 비용
        dp = new int[n][3]; //dp[i][j]: 0번째부터 i번째 집까지 칠할 때 들어가는 비용(i번째 집의 색깔은 j)
        for(int i = 0; i<n; i++) {
            str = new StringTokenizer(br.readLine());
            for(int j = 0; j<3; j++) {
                a[i][j] = Integer.parseInt(str.nextToken());            
            }
        }
        pmax = 1000 * n + 1; //pmax: 0번째 집을 정해진 색깔이 아닌 다른 색으로 칠할 때의 초기값
        ans = 1000001; //ans: 출력값
        for(int k = 0; k<3; k++) {
            for(int i = 0; i<3; i++) {
                if(i==k) dp[0][i] = a[0][i]; //k=0(빨강), k=1(초록), k=2(파랑)
                else dp[0][i] = pmax;
            }
            for(int i = 1; i<n; i++) {
                dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + a[i][0];
                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + a[i][1];
                dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + a[i][2];
            }
            for(int i = 0; i<3; i++) {
                if(i==k) continue; //0번째 집을 칠한 색과 마지막 집을 칠한 색이 같지 않아야함
                ans = Math.min(ans, dp[n-1][i]);
            }            
        }
        System.out.println(ans);        
    }
}