BOJ 1006 - 습격자 초라기

문제

• \(2 \times n(1 \le n \le 10000)\)으로 나눠진 구역의 끝부분이 원형으로 연결되어 있다.
• 한 소대의 인원수 \(W(1 \le W \le 10000)\)와 각 구역 내부 적의 수 \(s_i (1 \le s_i \le W)\)가 주어질 때, 아래 조건에 따라 모든 구역을 커버하는데 필요한 소대의 최솟값을 구해야 한다.
  • 한 소대는 침투한 구역 외에 상하좌우 중 한 구역을 더 커버할 수 있다.
  • 각 구역에는 하나의 소대만 있어야 한다.(\(s_{0, 1}\), \(s_{0, 3}\)의 소대원들을 합해서 \(s_{0, 2}\) 구역을 커버하게 배치할 수 없다.)
  • 한 소대가 커버하는 구역의 적들의 합은 \(W\) 이하여야 한다.

풀이

• 각 구역에 침투하는 소대를 \(\text{A, B, C,} \dots\)라고 하면, 아래와 같이 경우를 나눌 수 있다.

\[\begin{split} &\begin{array}{l c|c} 1. & ? & A \\ & ? & B \\ \end{array} \qquad\begin{array}{l c|c} 2. & ? & A \\ & ? & A \\ \end{array} \qquad\begin{array}{l c|c} 3. & A & A \\ & ? & B \\ \end{array} \\ &\begin{array}{l c|c} 4. & ? & A \\ & B & B \\ \end{array} \qquad\begin{array}{l c|c} 5. & A & A \\ & B & B \\ \end{array} \end{split}\]

• 위 \(\vert\)를 기준으로 오른쪽을 i번째 열이라 할때, 상태 공간 dp[i][1], ..., dp[i][5]를 각각 i번째 열까지 소대를 배치하고, i번째 열이 1, ..., 5와 같은 상황일 때 필요한 최소 소대 수라고 정의할 수 있다.
• ar[j][i]를 j행 i열 구역의 적의 수라고 하면, 아래와 같이 점화식을 정의할 수 있다.

\[\begin{aligned} &dp(i)(1) = \text{min(dp(i-1)(1), }\dots \text{, dp(i-1)(5))}+2 &&\\ &dp(i)(2) = dp(i)(1)-1, && \text{if } ar(0)(i) + ar(1)(i) \le W \\ &dp(i)(3) = \text{min(dp(i-1)(1), dp(i-1)(4))}+1, && \text{if } ar(0)(i-1) + ar(0)(i) \le W \\ &dp(i)(4) = \text{min(dp(i-1)(1), dp(i-1)(3))}+1, && \text{if } ar(1)(i-1) + ar(1)(i) \le W \\ &dp(i)(5) = dp(i-1)(0), && \text{if } ar(0)(i-1) + ar(0)(i) \le W \text{ and}\\ & && \phantom{\text{if }} ar(1)(i-1) + ar(1)(i) \le W \end{aligned}\]

• 그런데 만약 0번째 열이 \(5\)번째 상황으로 시작했는데, dp를 계산한 결과 dp[n-1][5]가 최솟값이라면, 이는 배치할 수 없는 경우이다.
  • 하나의 소대는 최대 2개의 영역에 들어가야 하지만, n-1 번째 열의 소대들은 n-2, 0번째 열의 배치 모두에 사용되었기 때문에, 두 번 계산된 셈이다.
• 따라서, 점화식의 첫 항을 0번째 열의 상태에 따라 점화식의 첫 항을 다르게 초기화하고, dp(n-1)의 최솟값을 구할 때 0번째 열에서의 n-1번째 열의 사용 여부를 확인해서 중복 사용이 되지 않게 적절히 제외하고 계산해야 한다.
  • 0번째 열이 1 또는 2 상황일 경우 : dp[n-1]의 모든 값 비교
  • 0번째 열이 3 상황일 경우 : dp[n-1][1], dp[n-1][4]만 비교
  • 0번째 열이 4 상황일 경우 : dp[n-1][1], dp[n-1][3]만 비교
  • 0번째 열이 5 상황일 경우 : dp[n-1][0]만 비교
• 따라서 dp의 가장 앞에 0번째 열의 상황을 나타내는 상태 변수를 추가하였다.
  즉, dp[c][i][k]는 0번째 열이 c 상황일 때, i번째 열이 k 상황으로 소대 배치가 완료된 상태에서, 배치한 소대 수의 최솟값이다.
• 각 상황에 맞게 dp를 초기화하고 계산 후, 적절한 값들을 비교하면 된다.

코드

#include <algorithm>
#include <iostream>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc, n, w;
    cin >> tc;
    while (tc--) {
        cin >> n >> w;
        v<vi> ar(2, vi(n, 0));
        v<v<vi>> dp(4, v<vi>(n, vi(5, 9999999)));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) cin >> ar[i][j];
        }
        dp[0][0][0] = 2;
        if (ar[0][0] + ar[1][0] <= w) dp[0][0][1] = 1;
        if (ar[0][n - 1] + ar[0][0] <= w && n > 1) {
            dp[1][0][0] = 2;
            if (ar[0][0] + ar[1][0] <= w) dp[1][0][1] = 1;
            dp[1][0][2] = 1;
        }
        if (ar[1][n - 1] + ar[1][0] <= w && n > 1) {
            dp[2][0][0] = 2;
            if (ar[0][0] + ar[1][0] <= w) dp[2][0][1] = 1;
            dp[2][0][3] = 1;
        }
        if (dp[1][0][2] == 1 && dp[2][0][3] == 1 && n > 1) {
            dp[3][0][0] = 2;
            if (ar[0][0] + ar[1][0] <= w) dp[3][0][1] = 1;
            dp[3][0][2] = 1;
            dp[3][0][3] = 1;
            dp[3][0][4] = 0;
        }

        for (int c = 0; c < 4; c++) {
            for (int i = 1; i < n; i++) {
                bool f0 = ar[0][i - 1] + ar[0][i] <= w, f1 = ar[1][i - 1] + ar[1][i] <= w;
                dp[c][i][0] = *min_element(dp[c][i - 1].begin(), dp[c][i - 1].end()) + 2;
                if (ar[0][i] + ar[1][i] <= w) dp[c][i][1] = dp[c][i][0] - 1;
                if (f0) dp[c][i][2] = min(dp[c][i - 1][0], dp[c][i - 1][3]) + 1;
                if (f1) dp[c][i][3] = min(dp[c][i - 1][0], dp[c][i - 1][2]) + 1;
                if (f0 && f1) dp[c][i][4] = dp[c][i - 1][0];
            }
        }

        int res = *min_element(dp[0][n - 1].begin(), dp[0][n - 1].end());
        res = min({res, dp[1][n - 1][0], dp[1][n - 1][3], dp[2][n - 1][0], dp[2][n - 1][2], dp[3][n - 1][0]});
        cout << res << '\n';
    }
    return 0;
}

풀고나서

• 순환 구조에서 dp를 사용할 때는 초기 상태 설정이 중요하다는 것을 깨달았다.
  • 점화식은 잘 떠올렸지만, 초기 상태에 따라 나눠야 한다는 것을 몰라서 다른 풀이를 보고 풀었다. n-1과 0의 관계를 어떻게 고정해야 할지 고민하다가 봤기 때문에, 풀이 공감이 많이 되었고 각인이 잘 될 것 같다.