[DP] BOJ 1006 습격자 초라기

문제 링크 : www.acmicpc.net/problem/1006

1006번: 습격자 초라기

굉장히 난해하고 어려운 문제다. 그나마 쉽게 접근하기 위해 원형으로 제시된 각 구역들을 선형으로 생각해보자.

그리고 다음과 같이 정의한다.

 - dp[k][2] : k열의 0행, 1행에 해당하는 구역 모두에 소대를 배치하지 않은 상태를 만드는 데 필요한 최소 소대 수

 - dp[k][0] : k열의 0행까지만 소대를 배치한 상태를 만드는 데 필요한 최소 소대 수

 - dp[k][1] : k열의 1행까지만 소대를 배치한 상태를 만드는 데 필요한 최소 소대 수

 

위 정의에 의해, 다음이 성립한다.

dp값은 최소 소대 수를 의미하기 때문에, 이미 배치된 구역에 대해 인접 구역은 고려하지 않았음에 주의하자.

인접 구역을 같이 배치한 경우는 다음과 같이 계산할 수 있다.

배열 e는 각 구역에 존재하는 적의 수를 의미한다.

k열의 0행, 1행을 모두 채우는 경우(즉, dp[k + 1][2])는 다음과 같은 경우가 존재한다.

 - k - 1열, k열의 0행이 인접 배치가 가능하며, k - 1열, k열의 1행 또한 인접 배치가 가능한 경우

k - 2열까지 모두 채운 경우(즉, dp[k - 1][2])에서 소대를 둘 더 배치하는 것과 같다.

따라서 dp[k + 1][2] = min(dp[k + 1][2], dp[k - 1][2] + 2)이 성립한다.

 

 - k열의 0행, 1행이 인접 배치가 가능한 경우

k - 1열까지 모두 채운 경우(즉, dp[k][2])에서 소대를 하나 더 배치하는 것과 같다.

따라서 dp[k + 1][2] = min(dp[k + 1][2], dp[k][2] + 1)이 성립한다.

 

k열의 두 행 중 한 구역만 채워진 경우도 인접 배치를 다음과 같이 고려할 수 있다.

이제 점화식은 구했지만, 우리는 이 점화식을 구하기 위해 제시된 원형 구역을 선형으로 간주했었다.

만약 각 구역을 원형으로 생각한다면, 1행과 N행을 인접 배치하는 경우까지 생각해주어야 한다.

우리가 선형으로 생각해 구한 답은 위와 같다.

1열과 N열이 인접 배치가 불가능한 경우는 선형으로 생각해 구한 답과 동일하다. 따라서 초기값은 위와 같다.

정답은 N열까지 모두 채우는 최소 소대 수인 dp[n + 1][2]가 된다.

이번에는 1열, N열이 0행에서 인접 배치가 가능한 경우이다. 인접 배치된 구역을 배제하고 초기값을 설정하면 위와 같다.

dp[2][2] : 1열을 모두 채우는 경우이므로, 1행 1열만 채우는 1이 된다.

dp[2][0] : 1열 1행과 2열 0행을 채우는 경우이므로 2가 된다.

dp[2][1] : 1열 1행과 인접 배치가 가능하다면 1, 그렇지 않으면 2가 된다.

이제 정답은 N열의 1행 구역까지만 채우는 최소 소대 수(dp[n][1])와 처음에 배제했던 1개 소대의 합인 dp[n][1] + 1이 된다.

마찬가지로 1열, N열이 1행에서 인접 배치가 가능한 경우이다.

dp[2][2] : 1열을 모두 채우는 경우이므로, 1행 0열만 채우는 1이 된다.

dp[2][0] : 1열 0행과 인접 배치가 가능하다면 1, 그렇지 않으면 2가 된다.

 

dp[2][1] : 1열 0행과 2열 1행을 채우는 경우이므로 2가 된다.

정답은 N열의 0행 구역까지만 채우는 최소 소대 수(dp[n][0])와 처음에 배제했던 1개 소대의 합인 dp[n][0] + 1이 된다.

마지막으로 1열과 N열이 각각 0행, 1행에서 인접 배치가 가능한 상황이다.

이 경우에는 2열부터 N - 1열만 있다고 가정한 후, 선형으로 생각한 결과와 같아진다.

정답은 N - 1열까지 모두 채우는 최소 소대 수인 dp[n][2]에 배제한 두 개의 소대를 더한 dp[n][2] + 2가 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
#define INF 99999
 
using namespace std;
 
int n, w;
int enemy[10001][2];        //0 : 아래, 1 : 위
int dp[10010][3];        //0 : 아래만, 1 : 위만, 2 : 모두 없음
 
void get_dp(int start) {
    for (int i = start; i <= n; i++) {
        //i번째 행에 대해 채워나간다.
 
        dp[i + 1][2] = min(dp[i][0] + 1, dp[i][1] + 1);
 
        if (enemy[i][0] + enemy[i][1] <= w)
            //i - 1까지 다 채운 후, i행 둘을 한번에 채움
            dp[i + 1][2] = min(dp[i + 1][2], dp[i][2] + 1);
 
        if (i > 0 && enemy[i - 1][0] + enemy[i][0] <= w && enemy[i - 1][1] + enemy[i][1] <= w)
            //i - 2까지 다 채운 후 가로로 둘씩
            dp[i + 1][2] = min(dp[i + 1][2], dp[i - 1][2] + 2);
 
        if (i == n) continue;
 
        dp[i + 1][0] = dp[i + 1][2] + 1;
        dp[i + 1][1] = dp[i + 1][2] + 1;
 
        //i - 1행까지 다 채우고 i행의 아래만 채워져있는 경우
        if (enemy[i][0] + enemy[i + 1][0] <= w)
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 1);
 
        //i - 1행까지 다 채우고 i행의 위만 채워져있는 경우
        if (enemy[i][1] + enemy[i + 1][1] <= w)
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 1);
    }
}
 
void init() {
    cin >> n >> w;
    memset(enemy, 0, sizeof(enemy));
 
    for (int i = 1; i <= n; i++) cin >> enemy[i][0];
    for (int i = 1; i <= n; i++) cin >> enemy[i][1];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
 
    for (int i = 0; i < tc; i++) {
        init();
        int answer = INF;
 
        dp[1][2] = 0;
        dp[1][0] = 1; dp[1][1] = 1;
        get_dp(1);
        answer = dp[n + 1][2];
 
        if (n > 2) {
            if (enemy[1][0] + enemy[n][0] <= w) {
                //1, n행이 아랫줄에 걸침
                dp[2][2] = 1;
                dp[2][0] = 2;
                dp[2][1] = enemy[1][1] + enemy[2][1] <= w ? 1 : 2;
                get_dp(2);
                answer = min(answer, dp[n][1] + 1);
            }
 
            if (enemy[1][1] + enemy[n][1] <= w) {
                //1, n행이 윗줄에 걸침
                dp[2][2] = 1;
                dp[2][0] = enemy[1][0] + enemy[2][0] <= w ? 1 : 2;
                dp[2][1] = 2;
                get_dp(2);
                answer = min(answer, dp[n][0] + 1);
            }
 
            if (enemy[1][0] + enemy[n][0] <= w && enemy[1][1] + enemy[n][1] <= w) {
                //n행, 1행을 각각 두 열씩 합침
                dp[2][2] = 0;
                dp[2][0] = 1;
                dp[2][1] = 1;
                get_dp(2);
                answer = min(answer, dp[n][2] + 2);
            }
        }
 
        printf("%d\n", answer);
    }
 
    return 0;
}