[C++] 1006번 습격자 초라기 - DP

1. 문제

• 초라기는 W명으로 구성된 특수 소대를 다수 출동시킨다. 2*N의 원형으로 된 원타곤에 각각 적이 몇 명 배치되어 있는지 알고 있다. 한 특수 소대는 특수 소대원의 수보다 작거나 같은 적을 커버할 수 있으며 인접한 한 곳을 포함해 최대 두 곳까지 커버 가능하다고 한다. 이때 초라기가 원타곤의 모든 구역을 커버하기 위해 침투시켜야 할 특수 소대의 최소 개수는?

<입력>

• -1-   테스트 케이스의 개수 T
• --1-   (구역의 개수)/2 값 N, 특수 소대원의 수 W \((1 \leq N \leq 10,000, 1 \leq W \leq 10,000)\)
• --2-   1~N번째 구역에 배치된 적의 수
• --3-   N+1~2N번째 구역에 배치된 적의 수. 단, 각 구역에 배치된 적의 수 <= W

<출력>

• 각 테스트케이스에 대해 원타곤에 침투시켜야 할 특수 소대의 최소 개수를 출력

2. 재정의

• 2*n의 원형 판을 합이 W이하가 되도록 최대 2개까지 인접해 묶어 그룹을 만들 수 있다. 그룹의 최소 수는?

3. 해결 방법

• 원형이므로 2*n의 직사각형으로 생각하되, 양 끝이 연결되어 있지 않은 경우, 가로 한 줄이 연결되어 있는 경우, 가로 두 줄이 연결되어 있는 경우 세로 한 줄이 연결되어 있는 경우를 시작부터 정해서 DP를 사용한다.
• DP를 해서 가능한 최솟값을 구함.

각 DP 케이스

4. 실수한 점, 개선할 점

• 양 끝 가로 위 한 줄이 연결되어 있는 경우, dp[N-1][1]만 생각하는 것이 아닌, dp[N-1][2]+1도 고려해야 한다.

 

<코드>

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 987654321;
const int MAX_N = 10001;

//테스트 케이스의 개수 T
int T;
//(구역의 개수)/2 N, 특수 소대원의 수 W
int N, W;
//원타곤
int map[2][MAX_N];
//DP(0: 위, 1: 아래, 2: X)
int dp[MAX_N][3];
int ret;

void DPreset() {
    for(int i=0; i<MAX_N; i++)
        for(int j=0; j<=2; j++)
            dp[i][j] = INF;
}

void input() {
    cin >> N >> W;
    
    for(int i=0; i<2; i++)
        for(int j=1; j<=N; j++)
            cin >> map[i][j];
    
    ret = INF;
    DPreset();
}

void dynamic_programming(int ca, int N) {
    switch(ca) {
        case 0:
            dp[0][0] = dp[0][1] = INF;
            dp[0][2] = 0;
            break;
        case 1:
            dp[0][1] = dp[0][2] = INF;
            dp[0][0] = 1;
            break;
        case 2:
            dp[0][0] = dp[0][2] = INF;
            dp[0][1] = 1;
            break;
        case 3:
            dp[0][0] = dp[0][1] = dp[0][2] = INF;
            dp[1][2] = 2;
    }
    
    for(int i=1; i<=N; i++) {
        //위 가로, 아래 가로, 세로 합이 W보다 작은가?
        bool uflag, dflag, pflag;
        uflag = dflag = pflag = false;
        if(map[0][i] + map[0][i+1] <= W) uflag = true;
        if(map[1][i] + map[1][i+1] <= W) dflag = true;
        if(map[0][i] + map[1][i] <= W) pflag = true;
        //아무 것도 아닌 경우
        dp[i][2] = min({dp[i][2], dp[i-1][1] + 1, dp[i-1][0] + 1, dp[i-1][2] + 2});
        
        //위 가로
        if(uflag)
            dp[i][0] = min({dp[i][0], dp[i-1][2] + 2, dp[i-1][1] + 1});
        //아래 가로
        if(dflag)
            dp[i][1] = min({dp[i][1], dp[i-1][2] + 2, dp[i-1][0] + 1});
        //세로
        if(pflag)
            dp[i][2] = min({dp[i][2], dp[i-1][2] + 1});
        //위 아래 둘 다 가로
        if(uflag && dflag)
            dp[i+1][2] = min(dp[i+1][2], dp[i-1][2] + 2);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    
    while(T--) {
        input();
        
        //위 가로, 아래 가로 합이 W보다 작은가?
        bool uflag, dflag;
        uflag = dflag = false;
        if(map[0][1] + map[0][N] <= W) uflag = true;
        if(map[1][1] + map[1][N] <= W) dflag = true;
        
        //cout << uflag << dflag << '\n';
        
        //양 끝을 연결하지 않은 경우
        dynamic_programming(0, N);
        ret = min(ret, dp[N][2]);
        DPreset();
        
        //양 끝 위를 연결한 경우
        if(uflag) {
            dynamic_programming(1, N-1);
            ret = min({ret, dp[N-1][2]+1, dp[N-1][1]});
            DPreset();
        }
        
        if(dflag) {
            dynamic_programming(2, N-1);
            ret = min({ret, dp[N-1][2]+1, dp[N-1][0]});
            DPreset();
        }
        
        if(uflag && dflag) {
            dynamic_programming(3, N-1);
            ret = min(ret, dp[N-1][2]);
            DPreset();
        }

        cout << ret << '\n';
    }
    
    return 0;
}

 

<테스트 케이스>

https://www.acmicpc.net/board/view/83667

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.