(Java) 백준 17404

백준 17404

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	20344	12122	10020	59.796%

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

답안

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

public class BOJ17404 {
    public static void main(String[] args) throws IOException {
		// N 입력 받기
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        // 비용 입력 받기
        int[][] weights = new int[n][3];
        for (int i = 0; i < n; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < 3; j++) {
                weights[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
        // 최초 선택 정보, 각 숫자, 선택한 컬러
        // memo[0-2][0][0-2]에서부터 memo[0-2][2][0-2]까지 initialize
        int[][][] memo = new int[3][n][3];
        // 첫 번째 숫자
        for (int k = 0; k < 3; k++) {
            for (int j = 0; j < 3; j++) {
                memo[k][0][j] = weights[0][j];
            }
        }
        // 두 번째 숫자
        for (int k = 0; k < 3; k++) {
            for (int j = 0; j < 3; j++) {
                memo[k][1][j] = weights[1][j] + memo[k][0][k];
            }
        }
        // N이 2인 경우 out of index 막기 위해 조기 종료
        if (n == 2) {
            int answer = Integer.MAX_VALUE;
            answer = Math.min(answer, Math.min(memo[0][1][1], memo[0][1][2]));
            answer = Math.min(answer, Math.min(memo[1][1][0], memo[0][1][2]));
            answer = Math.min(answer, Math.min(memo[2][1][0], memo[0][1][1]));
            System.out.println(answer);
            return;
        }
        // 세 번째 숫자
        for (int k = 0; k < 3; k++) {
            memo[k][2][k] = weights[2][k] + Math.min(memo[k][1][(k+1)%3], memo[k][1][(k+2)%3]);
            memo[k][2][(k+1)%3] = weights[2][(k+1)%3] + memo[k][1][(k+2)%3];
            memo[k][2][(k+2)%3] = weights[2][(k+2)%3] + memo[k][1][(k+1)%3];
        }

		// DP
        int answer = Integer.MAX_VALUE;
        for (int k = 0; k < 3; k++) {
            for (int i = 3; i < n; i++) {
                for (int j = 0; j < 3; j++) {
                    memo[k][i][j] = weights[i][j] + Math.min(memo[k][i-1][(j+1)%3], memo[k][i-1][(j+2)%3]);
                }
            }
            answer = Math.min(answer, memo[k][n-1][(k+1)%3]);
            answer = Math.min(answer, memo[k][n-1][(k+2)%3]);
        }

		// 답 출력
        System.out.println(answer);
    }
}

풀이

DP를 이용해 문제를 풀었다.

이때, DP에서 관리하는 상태로

1. 첫 번째로 선택한 색깔
2. 이전에 선택한 색깔이 x였을 때 그 색깔에 도달했을 때까지의 최소 비용 합

을 정해 풀었다.

DP를 선택한 이유는, 하나의 큰 문제가 1..N, 1..N-1, 1..N-2, …의 작은 하위의 문제로 나눠질 수 있기 때문이다. 즉, N개의 집에서의 최소 비용을 구하기 위해 N-1개의 집에서의 최소 비용 값을 이용할 수 있고, 이와 같이 계속 2개의 집, 1개의 집에서의 최소 비용 값을 이용하도록 나눠질 수 있다.

예를 들어 1번째 집에서 각각 R, G, B 색을 선택했을 때의 각각의 최소 비용 값이 이미 구해졌다고 가정했을 때, 2번째 집에서 R 색을 선택했을 때는 바로 이전의 1번째 집에서 G, B를 선택했을 때의 최소 비용 값 중 더 적은 것에 지금의 집을 색칠하는 비용을 더하면 된다. 이는 2번째 집에서 각각 G, B를 선택했을 때도 유사하게 처리 가능하며, 이와 같이 3번째 집, 4번째 집도 같은 방식으로 R, G, B를 색칠했을 때의 각각의 최소 비용 값을 구할 수 있다.

1개의 집에서의 최소 비용을 구하기 위해서는 $O(1)$번의 연산이 필요하므로, $O(n)$이라는 짧은 시간 안에 문제를 처리할 수 있어 문제 조건에서 주어진 짧은 시간 제한을 충족하기에도 용이하다.

다만, 문제에서는 아래 조건을 충족하는 것을 요구하고 있다.

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

위 조건에서 만약 1..N개의 집에서의 최소 비용을 구했다고 하더라도, 만약 1번 집의 색이 N번 집의 색과 같다면 그것은 invalid하게 된다. 1번 집의 색이 N번 집의 색과 같지 않은 조건 하에서 최소 비용을 구해야 하므로, 1번 집에서 어떤 색을 선택하였는지를 저장해, 이후 N번 집까지의 최소 비용을 구한 뒤 이 조건을 이용해 필터링해줄 필요가 있다.

int answer = Integer.MAX_VALUE;
for (int k = 0; k < 3; k++) {
    for (int i = 3; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            memo[k][i][j] = weights[i][j] + Math.min(memo[k][i-1][(j+1)%3], memo[k][i-1][(j+2)%3]);
        }
    }
    answer = Math.min(answer, memo[k][n-1][(k+1)%3]);
    answer = Math.min(answer, memo[k][n-1][(k+2)%3]);
}

위는 DP 알고리즘에서 가장 핵심적인 점화식이 위치한 부분이다.

이때 k는 첫 번째 집에서 선택한 색(R=0, G=1, B=2), i는 집의 인덱스, j는 i번 집까지가 j의 색으로 칠해졌을 때의 최소 비용 합을 뜻한다.

memo[i][j] = weights[i][j] + Math.min(memo[i-1][(j+1)%3], memo[i-1][(j+2)%3]

우선 3중첩 for 문 안에서는 k의 값과 무관하게 처리가 이뤄지므로 위와 같이 k를 없앤 상태에서 생각해보면, 이전에 선택했던 색을 다시 선택할 수 없으면서 이전의 최소 비용 합 중 더 적은 것을 선택하도록 하고 있다.

즉, 현재의 최소 비용 합(memo[i][j])은 현재 처리하고 있는 집을 색칠하기 위해 j색을 선택했을 때의 비용(weights[i][j])과 이전까지의 최소 비용 합 중 가장 작은 것(Math.min(memo[i-1][…], memo[k][i-1][…]))이다. 이때 이전까지의 최소 비용 합을 선택할 때, 바로 이전에 선택했던 색을 현재에 똑같이 선택할 수 없으므로 (j+1)%3번째와 (j+2)%3번째 색 중에서만 선택하도록 한다.

int answer = Integer.MAX_VALUE;
for (int k = 0; k < 3; k++) {
		...
		answer = Math.min(answer, memo[k][n-1][(k+1)%3]);
		answer = Math.min(answer, memo[k][n-1][(k+2)%3]);
}

그 다음으로는 문제의 답을 정하는 위 코드를 살펴보자.

첫 번째 집의 색을 R, G, B로 모두 칠해 보면서(k=0, k=1, k=2), 그 중 N번째 집(인덱스 = n-1)에서의 최소 비용(memo[…][n-1][…]) 중 최솟값을 구하고 있다. 이때, 첫 번째 집에서의 색깔(k)과 N번째 집에서의 색깔이 다른((k+1)%3, (k+2)%3) 경우만을 answer와 비교해 업데이트한다.

이외의 코드는 입력을 받고 메모이제이션 배열을 초기화하는 부분으로, 세부 설명은 코드에 주석으로 남겨 놓겠다.