[BOJ 17404] RGB거리 2 (Java)

BOJ 17404 RGB거리 2

난이도 : 골드 4

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

17404번: RGB거리 2

 

전략

전형적인 DP 문제이다.

 

i 번째 집을 j 색으로 칠하는 비용을 cost[i][j]라고 하자.

0번째 집 ~ i 번째 집을 칠할 때 i번째 집을 j 색으로 칠했을 때 최소 비용을 다음과 같은 점화식으로 표현할 수 있다.

dp[i][j] = cost[i][j] + min( {dp[i - 1][j가 아닌 색] } )

 

여기서 문제는 0번째 집과 N - 1번째 집의 색상도 달라야 한다는 것이다.

그래서 첫번째 집의 색을 하나로 고정시킨다.

이제 1 ~ N - 2 집에 대해서 DP를 수행하고 N - 1번째 집은 첫번째 집의 색상을 고를 수 없게 된다.

 

시행착오

첫번째 집의 색상을 고정시키는 startColor에 대해서 선택되지 않은 색상은 탐색이 되지 않도록 설정하고자 한다.

이 때 dp[0][ {startColor가 아닌 색상} ] = Integer.MAX_VALUE로 했었는데 DP 과정 중에서 + 연산에 의한 오버플로우가 발생했다.

 

따라서 최대 집 개수인 1000과 최대 비용인 1000을 곱한 100만보다 큰 임의의 수로 변경하여 오버플로우를 막으면서 startColor가 아닌 색이 선택되지 않도록 하였다.

 

코드

package BOJ_17404;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int n;
    static int[][] cost;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        cost = new int[n][3];

        for (int i = 0; i < n; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        System.out.println(solution());

    }

    static int solution() {
        int pickRed = search(0);
        int pickGreen = search(1);
        int pickBlue = search(2);

        return Math.min(Math.min(pickBlue, pickGreen), pickRed);
    }

    static int search(int startColor) {
        int[][] dp = new int[n][3];
        for (int i = 0; i < 3; i++) {
            if (i == startColor)
                dp[0][i] = cost[0][i];
            else
                dp[0][i] = 2_000_000;
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = cost[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]); // red
            dp[i][1] = cost[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]); // green
            dp[i][2] = cost[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]); // blue
        }

        for (int i = 0; i < 3; i++) {
            if (i == startColor)
                dp[n - 1][i] = Integer.MAX_VALUE;
        }

        return Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }
}

 

깨달은 점

처음에는 0번째 집과 N - 1번쨰 집이 순환되는 구조를 어떻게 풀어나가야될지 고민을 했다.

이럴 때는 가장 간단한 형태로 구현하고 조건을 추가하는 것이 방법일 수 있구나 생각했다.