[Java] 백준 BOJ / 17404번: RGB거리 2

RGB거리 2

문제

---

문제 설명

기존의 RGB거리 문제에서 조건이 추가된 문제이다.

추가된 조건은 이렇게 두가지 이다.

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

단순히 말하면 첫번째 집과 마지막 집의 색이 달라야 한다는 것이다.

기존에 풀었던 것처럼 DP를 사용해서 점화식을 세우고 풀면 된다.

---

구현

이 문제에서 dp[i][j]가 가지는 의미를 먼저 생각해보자.
만약에 dp[i][j] = X 라는 식이 있다면 그 의미는 아래와 같다.

1 ~ i 번째 집까지 칠하고 i 번째 집은 j 색으로 칠했을 때의 최소비용은 X 다.

이렇게 되면 j는 0부터 2까지 각각 R, G, B 를 뜻하고 첫 집과 마지막 집의 색깔이 같으면 안되기 때문에

1. 첫번째 집을 R로 색칠한 경우
   첫번째 집의 G, B의 DP 값을 무한대로 설정

2. 첫번째 집을 G로 색칠한 경우
   첫번째 집의 R, B의 DP 값을 무한대로 설정

3. 첫번째 집을 B로 색칠한 경우
   첫번째 집의 R, G의 DP 값을 무한대로 설정

이렇게 세가지 경우로 나누고 DP 각각의 경우로 계산한 DP 중 최솟값을 구하면 된다.

위와 같이 구현하기 위해 첫번째 집의 색깔을 정하기 위한 루프 변수 k 를 정하고 dp를 아래와 같이 초기화 한다.

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] = INF;
	}
}

그리고 루프 변수 i로 마지막 집까지 칠하는 경우를 구해주면 된다.

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];
}

이렇게 구하고 이번에 계산한 dp 값중 최소와 지금까지 구한 DP 값 중 최소를 저장하고 있는 ans 라는 변수 중 작은 값을 ans 로 초기화 해준다.

for (int i = 0; i < 3; i++) {
	if (i != k) {
		ans = Math.min(ans, dp[n][i]);
	}
}

---

코드

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

public class Main_17404 {
    static int n;
    static int[][] arr;
    static int[][] dp;
    static int INF = 1000 * 1000;
    static int ans = INF;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        arr = new int[n + 1][3];
        dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }

        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] = INF;
            }

            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);
    }
}