[백준 1006] 습격자 초라기

 

 

 DP 문제인데, 구현도 굉장히 빡빡한 문제. 문제를 천천히 읽다 보면 DP를 사용해야겠다는 것은 금방 떠오르는데, 그 이후가 말랑하지 않은 문제이다.

 먼저 배치된 소대의 최소 개수를 구하는 점화식을 생각해주어야 하는데, 거꾸로 생각을 해보는 것이 편하다. 일단 원타곤이 원형 배열이라는 것은 인지만 한 상태로 점화식부터 빠르게 찾기 위해 직선의 2차원 배열로 생각한다. 그렇게 되면, N 및 2N번째 구역이 위치한 열까지 소대를 배치했을 때 그 최솟값을 도출해야 하는 하는 문제가 된다. 이때, 마지막 열을 채우는 케이스는 아래와 같다.

 

 두 구역에 걸쳐 소대를 배치 가능한지 여부는 매번 W값과 인접한 적의 합을 통해 판별할 수 있고, 결국 매번 메모이제이션을 통해 저장해두어야 하는 것은 이전까지 소대가 배치된 상태별 최소 투입 소대 수이다. 그리고 나올 수 있는 패턴을 잘 관찰해 보면 이전까지 소대가 배치된 상태는 총 3가지로 생각할 수 있다.

 1번처럼 안쪽 행이 튀어나온 모양, 2번처럼 바깥쪽 행이 튀어나온 모양, 3~5번처럼 두 행 모두 채워져서 평탄한 모양. 물론 임의의 방향을 안쪽과 바깥쪽이라고 지정한 것이고, 반대로 바꿔도 상관은 없다. 그리고 3번과 4, 5번이 다르다고 생각할 수 있지만, 그 이전 열에 대해 메모이제이션 해둔 값을 사용하면 되니까 해당하는 열에 대해 꽉 찬 모양만 생각하면 된다.

 

 따라서 dp 테이블에는 총 3개의 행이 필요하고, 나는 dp[0][]과 dp[1][]를 각각 한쪽 방향이 튀어나온 모양으로 두고, dp[2][]를 두 곳 모두 꽉 찬 모양으로 두었다. 이제 점화식 세우는 것은 비교적 간단하다.

 

 dp[0][i]는 arr[0][i]+arr[0][i-1] <= w 일 때, min(dp[1][i-1]+1, dp[2][i-1]+1)이고, 아니라면 dp[2][i-1]+1이다. dp[1][i-1]+1는 1번 케이스에서 초록색 부분을 뺀 모양새이고, dp[2][i-1]+1는 4번 케이스에서 초록색 부분을 뺀 모양새라고 생각하면 된다.

 dp[1][i]는 dp[0][i] 케이스와 튀어나온 방향만 반대로 생각해 주면 된다.

 dp[2][i]는 먼저 arr[0][i]+arr[1][i] <= w 인지 확인한다. 같은 열에 함께 소대를 배치할 수 있는지를 검사하는 것이다. 만약 가능하다면 min(dp[2][i-1]+1, min(dp[0][i]+1, dp[1][i]+1))을 구한다. dp[2][i-1]+1는 5번 케이스이고, 뒤에 오는 min(dp[0][i]+1, dp[1][i]+1)은 1번, 2번, 4번 케이스를 고려해 주는 것이다.

 만약 불가능 하다면 5번 케이스는 고려하지 않아도 되니까, min(dp[0][i]+1, dp[1][i]+1)만 구해준다.

 이걸로 끝이 아닌데, 3번 케이스를 따져줘야 한다. arr[0][i]+arr[0][i-1] <= w이고, arr[1][i]+arr[1][i-1] <= w인 경우라면, 좀 전까지 구해둔 dp[2][i]에 대해 min(dp[2][i], dp[2][i-2]+2)를 구해준다. 이때 i-2에 접근하므로, 인덱싱할 때 주의해주어야 한다.

 

 여기까지 구하면 dp[2][i]에는 i번 째 열까지, 소대를 모두 배정했을 때 최소한으로 배치한 소대 수가 저장되게 된다.

 

 이제 다음으로 생각해야 하는 것은 원타곤이 원형 배열이라는 점이다. 일반적으로 이런 원형 배열에 대한 DP 문제를 풀 때는 나올 수 있는 케이스들을 나누어 따로따로 DP 테이블을 계산해 보는 것이 편하기 때문에, 나는 그 방법을 사용했다.

 

 나는 케이스를 총 4가지로 나누어 생각했다.

- 1번째 열과 N번째 열에 함께 배치된 소대가 없는 경우

- 1번째 열과 N번째 열의 안쪽 행에 한 소대를 배치하는 경우

- 1번째 열과 N번째 열의 바깥쪽 행에 한 소대를 배치하는 경우

- 1번째 열과 N번째 열의 두 행 모두 각각 함께 한 소대씩 배치하는 경우

 

 첫 번째 케이스는 항상 고려해야 하고, 나머지 케이스들은 W값과 비교해서 실제로 배치가 가능한 경우에만 고려해 준다. 이제 이 상태값들을 이용하면 dp테이블의 초기값을 채워준다. 그러고 나서 위에 구해둔 점화식으로 dp 테이블을 모두 구하고 나서 다시 저 상태값들을 참조해 적절한 값을 확인해 주면 된다.

 1번째 케이스라면, dp[2][n-1](0..n-1 기준)을 확인하면 되고,

 2번째 케이스라면, dp[1][n-1]을 확인하면 되고,

 3번째 케이스라면, dp[0][n-1]을 확인하면 되고,

 4번째 케이스라면, dp[2][n-2]를 확인하면 된다.

 

 DP 테이블의 각 행이 나타내는 모양새를 떠올리면, 왜 그렇게 확인해야 하는지는 쉽게 생각할 수 있다. 그리고 마지막으로 구현 디테일에 따라 달라지겠지만, 원타곤의 길이가 1인 경우나 아까처럼 잘못된 인덱싱을 할 우려가 있는 부분 등을 체크하거나 분기처리 해준 후에 마무리 한다.

 조금 집중력이 흐트러지면 엣지 케이스를 놓치기 쉬운 문제인 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) {
        int n, w;
        cin >> n >> w;
        
        vector<vector<int> > enemyList(2, vector<int>(n)); //{{innerArr}, {outerArr}};
        for(int i=0; i<n; i++) {
            cin >> enemyList[0][i];
        }
        for(int i=0; i<n; i++) {
            cin >> enemyList[1][i];
        }

        if(n==1) {
            cout << (enemyList[0][0] + enemyList[1][0] <= w ? 1 : 2) << "\n";
            continue;
        }

        vector<pair<int, int> > initFlags; //{innerConnected, outerConnected};
        initFlags.push_back({false, false});
        if(enemyList[0][0]+enemyList[0][n-1]<=w) {
            initFlags.push_back({true, false});
        }
        if(enemyList[1][0]+enemyList[1][n-1]<=w) {
            initFlags.push_back({false, true});
        }        
        if(enemyList[0][0]+enemyList[0][n-1]<=w && enemyList[1][0]+enemyList[1][n-1]<=w) {
            initFlags.push_back({true, true});
        }   
        
        int minNum = INF;

        for(auto initCase: initFlags) {
            vector<vector<int> > dp(3, vector<int>(n, INF));
            dp[0][0] = initCase.second ? INF : 1;
            dp[1][0] = initCase.first ? INF : 1;
            dp[2][0] = (!initCase.first && !initCase.second && (enemyList[0][0] + enemyList[1][0] <= w)) ? 1 : 2;

            for(int i=1; i<n; i++) {
                bool innerFlag = enemyList[0][i-1] + enemyList[0][i] <= w;
                bool outerFlag = enemyList[1][i-1] + enemyList[1][i] <= w;
                bool verticalFlag = enemyList[0][i] + enemyList[1][i] <= w;

                if(innerFlag) {
                    dp[0][i] = min(dp[1][i-1]+1, dp[2][i-1]+1);
                } else {
                    dp[0][i] = dp[2][i-1]+1;
                }

                if(outerFlag) {
                    dp[1][i] = min(dp[0][i-1]+1, dp[2][i-1]+1);
                } else {
                    dp[1][i] = dp[2][i-1]+1;
                }

                if(verticalFlag) {
                    dp[2][i] = min(dp[2][i-1]+1, min(dp[0][i]+1, dp[1][i]+1));
                } else {
                    dp[2][i] = min(dp[0][i]+1, dp[1][i]+1);
                }
                if(innerFlag && outerFlag) {
                    if(i>1) {
                        dp[2][i] = min(dp[2][i], dp[2][i-2]+2);
                    } else if(!initCase.first && !initCase.second) {
                        dp[2][i] = min(dp[2][i], 2);
                    }

                }
            } 

            if(initCase.first && initCase.second) {
                minNum = min(minNum, dp[2][n-2]);
            } else if(initCase.first) {
                minNum = min(minNum, dp[1][n-1]);
            } else if(initCase.second) {
                minNum = min(minNum, dp[0][n-1]);  
            } else {
                minNum = min(minNum, dp[2][n-1]);
            }
        }

        cout << minNum << "\n";
    }

}