습격자 초라기( BOJ 1006 )

문제 : https://www.acmicpc.net/problem/1006

1006번: 습격자 초라기

 

문제 파악하기

원형으로 생긴 구역에 특수 소대를 효율적으로 배치하는 문제입니다. 구역이 원형으로 생겼다는 점에 초점을 맞춰서 탐색을 시작해야 합니다. 우선, 시작 구역과 종료 구역이 겹치는 경우를 파악한 다음 해당 케이스마다 탐색을 진행하여 배치하는 특수 소대의 최솟값을 구하면 문제를 해결할 수 있습니다.

 

문제 해결하기

그렇다면 우선 첫 번째로 해야할 일은 시작 구역과 종료 구역이 겹치는 경우를 파악하는 것입니다. 나올 수 있는 경우는 하나도 겹치지 않는 경우부터 위/아래 모두 겹치는 경우까지 총 4가지 경우가 있습니다. 우리는 이를 2진법으로 이용하여 반복문으로 처리할 수 있습니다.

 

    // 0 - 3으로 첫 번째 필드 표현
    int p;
    for(bit=0;bit<4;bit++) {
        p = 1;
        for(int t=0;t<2;t++) {
            if( (bit & (1<<t)) and inp[N-1][t]+inp[0][t] > W ) p = 0;
        }
 
        if(p == 0) continue;
        else {
            memset(dp, -1, sizeof(dp));
 
            switch(bit) {
                case 0:
                    ret = min( ret, sv(0, bit) );
                    break;
 
                case 1:
                    ret = min( ret, sv(0, bit)+1 );
                    break;
 
                case 2:
                    ret = min( ret, sv(0, bit)+1 );
                    break;
 
                default:
                    ret = min( ret, sv(1, 0)+2 );
            }
        }
    }

 

이후, 각각의 경우에 해야할 일은 명확합니다. 현재 위치에 소대를 배치하되 한번 더 소대를 배치할 수 있는지를 확인하면 됩니다. 소대는 인접한 모든 구역에 배치할 수 있으나, 중복되는 경우를 제거하기 위해서는 항상 소대를 현재 위치에서 오른쪽 혹은 아래쪽으로만 배치할 수 있다고 가정하면 됩니다. 이렇게 나올 수 있는 모든 경우를 탐색하면서 메모이제이션을 통해 중복된 계산을 없애면 빠르고 정확하게 문제를 해결할 수 있습니다.

 

그럼 문제를 해결하는 재귀 함수를 설계해봅시다. 우선, 원형에서 현재 열을 표시하는 idx 매개 변수가 필요합니다. 그리고 현재 가리키고 있는 두 구역에 소대가 배치되었는지 여부를 표시하는 cur 매개 변수가 필요합니다. cur 변수가 있어야 이전에 오른쪽으로 부대를 배치한 경우 반영할 수 있기 때문입니다. 그리고 함수에서는 idx의 위치에 따라 값이 달라지는 nxt 변수가 있어야 합니다. nxt 변수는 다음 열의 소대 배치 상태를 나타낸 것으로 평소에는 항상 0입니다. 하지만 idx가 (N-2), (N-1)일 경우에는 특정 값을 가지게 됩니다. (N-2)일 경우에는 우리가 처음 설정한 시작 지점과 종료 지점의 상태를 가지게 되며, (N-1)인 경우에는 모두 채워져있는 상태를 가지게 됩니다. 이렇게 3개의 변수를 사용하여 나올 수 있는 모든 경우의 수를 구하면 우리가 원하는 값을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define NMAX 10010
#define INF 0x7FFFFFFF
using namespace std;
 
int T, N, W;
int inp[NMAX][2];
 
int bit, ret;
int dp[NMAX*2][4];
int dx[2]={0,1}, dy[2]={1,0};
 
vector< int > ans;
 
bool safe(int x, int y, int check) {
    if(x==N or y==2 or (check & (2*x+y))) return 0;
    else return 1;
}
 
int sv(int idx, int cur) {
    int nxt;
 
    if(idx == N-2) nxt = bit;
    else if(idx == N-1) nxt = 3;
    else nxt = 0;
 
    if(dp[idx][cur] >= 0) return dp[idx][cur];
    else if(idx == N) return dp[idx][cur] = 0;
    else {
        int val;
 
        // 1*1 모두 배치
        switch(cur) {
            case 0:
                val = sv(idx+1, nxt)+2;
                break;
 
            case 1:
            case 2:
                val = sv(idx+1, nxt)+1;
                break;
 
            case 3:
                val = sv(idx+1, nxt);
        }
 
        // 1*2 1개 + 1*1 1개 배치
        int cnt=0;
        for(int k=0;k<2;k++) {
            if(cur & (1<<k) or nxt & (1<<k)) continue;
 
            if(inp[idx][k]+inp[idx+1][k] <= W) {
                // 이미 다른 칸이 채워진 경우(Ex. cur=1 or cur=2)
                if(cur>0) val = min( val, sv(idx+1, nxt | (1<<k))+1 );
 
                // 다른 칸이 채워지지 않은 경우(Ex. cur=0)
                else val = min( val, sv(idx+1, nxt | (1<<k))+2 );
 
                cnt++;
            }
        }
 
        // 1*2 2개 배치
        if(cnt==2) val = min( val, sv(idx+1, 3)+2 );
 
        // 2*1 1개 배치
        if(cur == 0 and inp[idx][0]+inp[idx][1] <= W) val = min( val, sv(idx+1, nxt)+1 );
 
        return dp[idx][cur] = val;
    }
}
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // init
        ret = INF;
 
        //input
        scanf("%d %d", &N, &W);
        for(int k=0;k<2;k++) {
            for(int i=0;i<N;i++) scanf("%d", &inp[i][k]);
        }
 
        // 0 - 3으로 첫 번째 필드 표현
        int p;
        for(bit=0;bit<4;bit++) {
            p = 1;
            for(int t=0;t<2;t++) {
                if( (bit & (1<<t)) and inp[N-1][t]+inp[0][t] > W ) p = 0;
            }
 
            if(p == 0) continue;
            else {
                memset(dp, -1, sizeof(dp));
 
                switch(bit) {
                    case 0:
                        ret = min( ret, sv(0, bit) );
                        break;
 
                    case 1:
                        ret = min( ret, sv(0, bit)+1 );
                        break;
 
                    case 2:
                        ret = min( ret, sv(0, bit)+1 );
                        break;
 
                    default:
                        ret = min( ret, sv(1, 0)+2 );
                }
            }
        }
 
        ans.push_back(ret);
    }
 
    for(int val:ans) printf("%d\n", val);
}
 
/*
1
8 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40
ans: 11
*/

후기

구역이 원형이라 조건을 설정하는데 까다로운 문제입니다. 하지만 비트 스크롤링을 떠올린다면 나름 어렵지 않게 풀 수 있다고 생각합니다.