[Baekjoon] 1006 – 습격자 초라기

📖 문제 이해하기

이 문제는 도넛 모양의 건물에 배치된 적들을 효율적으로 제압하기 위한 최소 특수소대 개수를 구하는 문제입니다. 건물은 내부 원과 외부 원으로 이루어진 이중 원형 구조이며, 각 원은 N개의 구역으로 나뉘어 총 2N개의 구역이 존재합니다.

특수소대는 W명으로 구성되며, 한 구역만 점령하거나 인접한 두 구역을 함께 점령할 수 있습니다. 여기서 인접이란 같은 경계를 공유하는 구역을 의미하며, 구체적으로는:

• 같은 원(내부 또는 외부)에서 바로 옆 구역
• 같은 각도 위치의 내부-외부 구역 쌍

예를 들어, 1번 구역은 2번, 8번(같은 원의 양 옆), 그리고 9번(반대편 원의 대응 구역)과 인접합니다.

핵심 제약은 다음과 같습니다. 한 특수소대가 커버하는 구역들의 적 수 합이 W 이하여야 하며, 각 구역은 정확히 하나의 소대에만 할당되어야 합니다. 또한 원형 구조이므로 마지막 구역과 첫 번째 구역도 인접합니다.

간단한 예시로 N = 3, W = 10이고 각 구역의 적 배치가 [5, 4, 3] (외부 원), [6, 7, 2] (내부 원)인 경우를 생각해봅시다. 하나의 소대가 외부 5번과 내부 6번 구역을 함께 커버할 수 있다면(5 + 6 ≤ 10이 아니므로 불가능), 각각 별도로 커버해야 합니다. 이런 식으로 최소 소대 개수를 찾아야 합니다.

🧠 순진한 접근과 그 한계

이 문제를 처음 접하면 자연스럽게 “모든 가능한 커버 조합을 시도해보자”는 생각이 듭니다. 각 구역마다 독립적으로 커버할지, 아니면 어떤 인접 구역과 묶을지를 결정하는 방식입니다. 구역 번호 순서대로 하나씩 처리하면서, 각 단계에서 가능한 선택지를 모두 탐색하는 재귀적 접근이 떠오릅니다.

하지만 이 방법은 심각한 문제가 있습니다. 각 구역마다 최소 3가지 선택(단독 커버, 오른쪽과 묶기, 대응 구역과 묶기)이 가능하므로, 2N개 구역에 대해 O(3<sup>2N</sup>)의 경우의 수가 발생합니다. N = 10000인 경우 이는 3<sup>20000</sup>에 달하는 천문학적 숫자로, 현실적으로 계산 불가능합니다.

더 큰 문제는 원형 구조에서 비롯됩니다. 선형 배열이라면 첫 구역부터 끝까지 순차적으로 처리하면 되지만, 도넛 모양에서는 마지막 구역의 결정이 첫 번째 구역에 영향을 미칩니다. 예를 들어 마지막 구역을 단독으로 커버하기로 했다면 첫 번째 구역도 자유롭지만, 마지막과 첫 번째를 묶어서 커버하기로 했다면 첫 번째 구역은 이미 “예약된” 상태가 됩니다. 이런 순환 의존성 때문에 단순 재귀로는 올바른 답을 보장할 수 없습니다.

시간 복잡도뿐 아니라 논리적으로도, 순환 구조를 무시한 채 일방향으로만 진행하는 알고리즘은 시작점과 끝점의 연결 관계를 제대로 고려하지 못해 부정확한 결과를 낳을 수밖에 없습니다.

💡 돌파구: 순환을 선형으로 풀기

이 문제의 핵심 난관은 바로 원형 구조의 순환성입니다. 마지막 구역과 첫 번째 구역이 인접하기 때문에, 알고리즘이 진행되면서 내린 결정들이 서로 모순을 일으킬 수 있습니다. 이를 해결하는 열쇠는 “순환을 끊어 선형 문제로 변환하되, 나중에 경계 조건을 보정하는” 전략입니다.

먼저 원형 구조를 무시하고 0번부터 2N-1번까지를 일직선으로 배치된 것처럼 간주합니다. 이렇게 되면 우리가 익숙한 선형 DP 문제가 됩니다. N × 2 블록을 타일링하는 문제와 유사하게, 현재 위치와 바로 앞 몇 개 위치의 “커버 상태”만 기억하면서 전진할 수 있습니다.

하지만 여기서 중요한 통찰이 필요합니다. 원을 끊어서 선형으로 만들면, 끊어진 양 끝(마지막 구역과 첫 번째 구역)의 관계를 놓치게 됩니다. 따라서 우리는 끊어진 양 끝이 어떻게 처리될지를 미리 가정하고, 각 가정마다 별도로 DP를 실행해야 합니다.

구체적으로는 네 가지 시나리오를 고려합니다.

• 시나리오 1: 양쪽 끝을 묶지 않음
  마지막 구역들(외부 N-1번, 내부 N-1번)과 첫 번째 구역들(외부 0번, 내부 0번)이 서로 독립적으로 커버됩니다. 이것이 기본 케이스이며, 원형을 완전히 무시하고 선형 DP만 수행합니다.

• 시나리오 2: 외부 원의 끝과 시작을 묶음
  외부 원의 N-1번과 0번 구역을 하나의 소대가 커버한다고 가정합니다. 이 경우 N-1번 구역을 “이미 커버됨”으로 표시(적의 수를 0으로 설정)하고, 1번 구역부터 DP를 시작합니다. 0번 구역은 이미 N-1번과 묶여 있으므로 건너뛰며, 마지막에 이 묶음에 대한 소대 1개를 추가합니다.

• 시나리오 3: 내부 원의 끝과 시작을 묶음
  내부 원의 N-1번과 0번을 묶는 경우입니다. 마찬가지로 N-1번을 “커버됨”으로 처리하고, 0번 구역(내부 원 첫 구역)의 상태를 “이미 점령됨”으로 설정한 채 DP를 진행합니다.

• 시나리오 4: 양쪽 원 모두 끝과 시작을 묶음
  외부와 내부 원 모두에서 마지막과 첫 번째를 묶습니다. 두 구역 모두 “커버됨”으로 표시하고, 2번 구역(외부 1번)부터 DP를 시작합니다. 이 경우 2개의 소대가 양 끝을 담당하므로 결과에 2를 더합니다.

각 시나리오에서 계산된 최소 소대 개수 중 가장 작은 값이 최종 답이 됩니다. 이렇게 함으로써 순환 구조의 모든 가능성을 체계적으로 탐색하면서도, 각각은 선형 DP의 효율성을 유지할 수 있습니다.

📘 동적 계획법과 상태 압축
동적 계획법(DP)은 큰 문제를 작은 부분 문제로 쪼개고, 중복 계산을 피하기 위해 결과를 저장(메모이제이션)하는 기법입니다. 상태 압축은 DP에서 상태를 표현할 때, 비트마스크 등을 사용해 적은 메모리로 여러 조건을 동시에 인코딩하는 최적화 기법입니다. 이 문제에서는 현재 위치와 인접 구역들의 커버 상태를 3비트로 압축하여, dp[위치][상태]로 효율적으로 관리합니다.

DP 상태 설계의 핵심은 “현재 구역을 처리할 때 필요한 최소 정보만 기억하기”입니다. 우리는 현재 위치 curr (0부터 2N-1)과, 바로 앞 구역들의 커버 여부를 나타내는 3비트 상태를 사용합니다.

• 비트 0: 현재 위치의 2칸 뒤(같은 원의 이전 구역)
• 비트 1: 현재 위치의 1칸 뒤(반대편 원의 대응 구역)
• 비트 2: 현재 위치의 바로 앞 구역

자신보다 앞에 있는 이전 구역은 고려할 필요가 없습니다. 만약 이전 구역과 묶여 있는 경우는 현재 구역 이전에 이미 정해진 것이고, 만약 실제로 묶여 있다면, 현재 구역을 처리할때 비트 0이 이미 1로 세팅되어 있게 됩니다.

각 단계에서 현재 구역이 이미 커버되었는지 확인하고, 그렇지 않다면 가능한 커버 방법(단독, 같은 원의 다음 구역과 묶기, 반대편 원과 묶기)을 시도합니다. 상태는 매 단계 왼쪽으로 시프트되어 업데이트되며, 이를 통해 O(2N × 8) 크기의 메모이제이션 테이블로 효율적으로 계산할 수 있습니다.

🔍 알고리즘 상세 동작 예시

구체적인 예시로 N = 4, W = 10이고 다음과 같이 적이 배치되어 있다고 가정해봅시다.

• 외부 원(1~4번): [3, 5, 4, 2]
• 내부 원(5~8번): [6, 3, 7, 4]

코드에서는 좌표계를 (x, y) 형태로 관리하는데, x는 각도 위치(03), y는 원의 종류(0=내부, 1=외부)를 나타냅니다. 선형 인덱스 curr는 x*2 + y로 계산되어 07 범위를 가집니다.

시나리오 1: 기본 케이스 (양 끝 묶지 않음)

func(0, 0)부터 시작합니다. 상태 0b000은 앞의 모든 구역이 아직 처리되지 않았음을 의미합니다.

• curr = 0 (위치 (0,0), 내부 원 0번, 적 6명)
  상태: 0b000, 앞에 커버된 구역 없음
  선택지:
  1. 단독 커버: 소대 1개 사용, func(1, 0b000) 진행
  2. 같은 원 다음과 묶기(curr+2, 즉 내부 1번): 6 + 3 = 9 ≤ 10 가능
     → func(1, 0b001) (비트 0을 세트하여 2칸 뒤 커버됨 표시)
  3. 반대편 원과 묶기(curr+1, 외부 0번): 6 + 3 = 9 ≤ 10 가능
     → func(2, 0b000) (두 구역 동시 건너뜀)
  최적을 재귀적으로 탐색하여 최솟값 선택.
• curr = 1 (위치 (0,1), 외부 원 0번, 적 3명)
  이전 단계에서 내부와 묶였다면 이미 커버되어 func(2, ...)로 자동 진행.
  독립적이라면:
  1. 단독 커버: 소대 1개
  2. 다음 외부와 묶기(curr+2, 외부 1번): 3 + 5 = 8 ≤ 10
  3. 다음 내부와 묶기는 불가능 (이미 내부 1번은 처리됨)
• curr = 2 (위치 (1,0), 내부 원 1번, 적 3명)
  상태 비트에 따라 이미 커버되었는지 확인.
  커버 안 되었다면:
  1. 단독
  2. 내부 2번과 묶기: 3 + 7 = 10 ≤ 10 가능
  3. 외부 1번과 묶기: 3 + 5 = 8 ≤ 10 가능

이런 식으로 curr = 7까지 진행하면서, 각 단계의 최적값을 메모이제이션합니다. 예를 들어 dp[2][0b010]는 “위치 2에 도달했고, 1칸 뒤가 커버된 상태”에서의 최소 소대 수를 저장합니다.

시나리오 2: 외부 원 끝-시작 묶음

마지막 외부 구역(위치 (3,1), 적 2명)과 첫 외부 구역(위치 (0,1), 적 3명)을 묶는다고 가정합니다. 2 + 3 = 5 ≤ 10이므로 가능합니다.

• A[3][1] = 0으로 설정 (마지막 외부 이미 커버됨)
• func(1, 0b000)부터 시작 (첫 외부 건너뛰고 첫 내부부터)
• 최종 결과에 +1 (이 묶음에 소대 1개)

이렇게 계산된 값이 시나리오 1보다 작다면 갱신합니다.

시나리오 3: 내부 원 끝-시작 묶음

마지막 내부 구역(위치 (3,0), 적 4명)과 첫 내부 구역(위치 (0,0), 적 6명)을 묶습니다. 4 + 6 = 10 ≤ 10으로 가능.

• A[3][0] = 0으로 설정
• func(0, 0b010)부터 시작 (비트 1은 “1칸 뒤 커버됨”을 의미하며, 이는 다음 내부 구역이 예약됨을 뜻함)
• 최종 결과에 +1

시나리오 4: 양쪽 모두 묶음

외부와 내부 모두 끝-시작을 묶습니다.

• A[3][0] = A[3][1] = 0 설정
• func(2, 0b000)부터 시작 (처음 두 구역 모두 건너뜀)
• 최종 결과에 +2

네 시나리오 중 최솟값을 출력합니다. 이 예시에서는 시나리오별로 계산 결과가 다를 수 있으며, 적 배치에 따라 어떤 전략이 최적인지 달라집니다.

💻 전체 구현 코드

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 10000

int T, N, W;
<em>// A[x][y]: x는 각도 위치 (0~N-1), y는 원 종류 (0=내부, 1=외부)</em>
int A[MAX_N+1][2];

<em>// 비트마스크: 3비트만 사용 (2칸 뒤, 1칸 뒤, 바로 앞 구역의 커버 상태)</em>
int mask = (1 << 3) - 1;

<em>// dp[curr][state]: 현재 위치 curr, 상태 state일 때 필요한 최소 소대 수</em>
long long dp[2*MAX_N+1][1<<3];

<em>// 두 구역 a, b를 하나의 소대로 커버 가능한지 확인</em>
<em>// a, b는 선형 인덱스 (0~2N-1)</em>
bool check(int a, int b) {
   <em>// a를 (x, y) 좌표로 변환: x = a/2, y = a%2</em>
   return A[a/2][a%2] + A[b/2][b%2] <= W;
}

<em>// DP 재귀 함수: curr번 구역부터 끝까지 처리하는 최소 소대 수</em>
<em>// state: 3비트로 앞쪽 구역들의 커버 상태를 인코딩</em>
long long func(int curr, int state) {
   <em>// 모든 구역을 처리했으면 종료</em>
   if (curr == 2*N) return 0;
   
   <em>// 현재 구역의 좌표 추출</em>
   int x = curr / 2;  <em>// 각도 위치</em>
   int y = curr % 2;  <em>// 0=내부, 1=외부</em>
   
   <em>// 비트 2 (바로 앞 구역)가 세트되어 있거나, 적이 없는 구역이면 건너뜀</em>
   <em>// 적이 0이면 이미 다른 시나리오에서 "묶음" 처리된 것</em>
   if ((state & (1 << 2)) || A[x][y] == 0) 
      return func(curr+1, (state<<1) & mask);
   
   <em>// 메모이제이션: 이미 계산된 상태면 재사용</em>
   if (dp[curr][state] != -1) 
      return dp[curr][state];
   
   <em>// 선택지 1: 현재 구역을 단독으로 커버 (소대 1개 사용)</em>
   long long ans = func(curr+1, (state<<1) & mask) + 1;
   
   <em>// 선택지 2: 같은 원의 다음 구역(curr+2)과 묶기</em>
   <em>// 비트 0이 0이어야 하며 (2칸 뒤가 아직 커버 안 됨), </em>
   <em>// 두 구역 적의 합이 W 이하여야 함</em>
   if ((state & (1 << 0)) == 0 && check(curr, curr + 2)) {
      <em>// 상태를 왼쪽으로 시프트하고, 비트 0을 세트 (2칸 뒤 커버됨 표시)</em>
      ans = min(ans, func(curr+1, ((state | (1 << 0)) << 1) & mask) + 1);
   }
   
   <em>// 선택지 3: 반대편 원의 대응 구역(curr+1)과 묶기</em>
   <em>// y==0 (현재가 내부)이고, 비트 1이 0이어야 하며,</em>
   <em>// 두 구역 적의 합이 W 이하여야 함</em>
   if (y == 0 && (state & (1 << 1)) == 0 && check(curr, curr+1)) {
      <em>// 두 구역을 동시에 건너뛰므로 curr+2로 이동, 상태는 2칸 시프트</em>
      ans = min(ans, func(curr+2, (state << 2) & mask) + 1);
   } 
   
   <em>// 계산 결과를 메모이제이션 테이블에 저장</em>
   return dp[curr][state] = ans;
}

<em>// 메모이제이션 테이블 초기화</em>
void reset() {
   memset(dp, -1, sizeof(dp));
}

int main()
{
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   
   cin >> T;  <em>// 테스트 케이스 개수 입력</em>
   while(T--) {
      cin >> N >> W;  <em>// N: 각 원의 구역 수, W: 소대원 수</em>
      memset(A, 0, sizeof(A));
      
      <em>// 외부 원의 적 배치 입력 (1~N번 구역)</em>
      for (int i = 0; i < N; ++i) {
         cin >> A[i][1];
      }
      
      <em>// 내부 원의 적 배치 입력 (N+1~2N번 구역)</em>
      for (int i = 0; i < N; ++i) {
         cin >> A[i][0];
      }
      
      <em>// 시나리오 1: 기본 케이스 (양 끝 묶지 않음)</em>
      reset();
      long long ans = func(0, 0);
      
      <em>// 시나리오 2: 내부 원의 마지막과 첫 번째 묶기 가능 여부 확인</em>
      bool leftCan = A[N-1][0] + A[0][0] <= W;
      
      <em>// 시나리오 3: 외부 원의 마지막과 첫 번째 묶기 가능 여부 확인</em>
      bool rightCan = A[N-1][1] + A[0][1] <= W;
      
      if (leftCan) {
         reset();
         int tmp = A[N-1][0];  <em>// 백업</em>
         A[N-1][0] = 0;        <em>// 마지막 내부 구역을 "이미 커버됨"으로 표시</em>
         <em>// 1번부터 시작 (0번 내부는 마지막과 묶임)</em>
         ans = min(ans, func(1, 0) + 1);
         A[N-1][0] = tmp;      <em>// 복원</em>
      }
      
      if (rightCan) {
         reset();
         int tmp = A[N-1][1];
         A[N-1][1] = 0;        <em>// 마지막 외부 구역 커버됨 표시</em>
         <em>// 0번부터 시작하되, 상태 비트 1을 세트 (1칸 뒤, 즉 외부 0번이 예약됨)</em>
         ans = min(ans, func(0, 1 << 1) + 1);
         A[N-1][1] = tmp;
      }
      
      <em>// 시나리오 4: 양쪽 원 모두 끝-시작 묶기</em>
      if (leftCan && rightCan) {
         reset();
         A[N-1][0] = A[N-1][1] = 0;  <em>// 양쪽 모두 커버됨 표시</em>
         <em>// 2번부터 시작 (0, 1번 모두 묶임)</em>
         ans = min(ans, func(2, 0) + 2);
      }
      
      <em>// 네 시나리오 중 최솟값 출력</em>
      cout << ans << "\n";
   }
   
   return 0;
}

📌 핵심 통찰과 교훈

이 문제는 동적 계획법의 강력함과, 순환 구조를 다루는 기법을 잘 보여줍니다. 몇 가지 중요한 교훈을 정리하면 다음과 같습니다.

• 순환을 선형으로 변환하는 전략
  원형 구조는 시작점과 끝점이 연결되어 있어 DP를 직접 적용하기 어렵습니다. 하지만 “끝과 시작의 관계를 케이스로 나누고, 각 케이스를 선형으로 풀기”라는 기법으로 해결할 수 있습니다. 이는 순환 배열, 원형 경로, 링 구조 등의 문제에 폭넓게 적용되는 패턴입니다.

• 상태 압축의 효율성
  현재 결정에 영향을 미치는 과거 정보를 최소한으로 압축하는 것이 DP 설계의 핵심입니다. 이 문제에서는 바로 앞 3개 위치의 커버 상태만 필요했고, 이를 3비트로 인코딩하여 상태 공간을 극적으로 줄였습니다. 비트마스크는 이런 상황에서 매우 유용한 도구입니다.

• 타일링 문제와의 유사성
  이 문제는 본질적으로 N × 2 격자를 1×1, 1×2, 2×1 타일로 채우는 문제와 구조가 유사합니다. 다만 원형이라는 제약이 추가되었을 뿐입니다. 기존의 타일링 DP 패턴을 이해하고 있다면, 이를 확장하여 순환 구조에 적용할 수 있습니다.

• 경우 분석의 중요성
  복잡한 제약이 있을 때, 가능한 케이스를 체계적으로 나누고 각각을 독립적으로 해결하는 접근이 효과적입니다. 이 문제에서는 4가지 시나리오로 나누어 각각을 깔끔하게 처리했고, 이것이 코드의 정확성과 가독성을 모두 높였습니다.

• 알고리즘의 일반화
  이 문제의 아이디어는 다른 원형 DP 문제로 쉽게 일반화됩니다. 예를 들어 “원형 배열에서 인접하지 않은 원소의 최대 합”, “원형 경로에서의 최적 분할” 등의 문제에 동일한 패턴을 적용할 수 있습니다. 핵심은 항상 “순환을 끊고, 경계 조건을 케이스로 처리하기”입니다.