BOJ 1006:: 습격자 초라기

icpc.me/1006

아주 유명하고 어려운 문제입니다. 문제 목록 첫 페이지 최상단에 뜨는 문제라 순서대로 문제 푸는 초보자들을 좌절시키는 문제죠.

당연하게도 원형으로 된 배열이 주어지면 문제가 매우 어렵기 때문에, 건물이 $N\times2$짜리 직사각형인 경우를 먼저 풀어봅시다. 이렇게 되면 원타곤이 아니라 직타곤이라고 불러야 할까요…? 편의상 건물의 위쪽을 1행, 아래쪽을 2행이라 하고 왼쪽부터 차례로 0열부터 $N-1$열까지로 부르겠습니다.

먼저 동적 계획법을 사용하기 위해 세 배열을 다음과 같이 정의합니다.

  • $a_i$: 건물의 1행과 2행 모두 $i-1$열까지 특수소대로 채우는 데 필요한 특수소대의 수의 최솟값
  • $b_i$: 1행은 $i$열까지, 2행은 $i-1$열까지 채우는 데 필요한 특수소대의 수의 최솟값
  • $c_i$: 1행은 $i-1$열까지, 2행은 $i$열까지 채우는 데 필요한 특수소대의 수의 최솟값

그림으로 나타내면 아래와 같습니다. 회색이 특수소대로 채워진 구역, 흰색이 아직 채우지 않은 구역입니다.

이제 점화식을 구합시다. 1행과 2행 모두 $i$열까지 채우는 방법은

  1. 1행과 2행 모두 $i-1$열까지 채우고 1행 $i$열과 2행 $i$열에 특수소대 하나를 채움
  2. 1행과 2행 모두 $i-2$열까지 채우고 1행 $i-1$열과 1행 $i$열에 특수소대 하나, 2행 $i-1$열과 2행 $i$열에 특수소대 하나를 채움
  3. 1행은 $i$열까지, 2행은 $i-1$열까지 채우고 2행 $i$열에 특수소대 하나를 채움
  4. 1행은 $i-1$열까지, 2행은 $i$열까지 채우고 1행 $i$열에 특수소대 하나를 채움

다만 1번과 2번은 두 구역에 걸쳐 특수소대 하나를 채우는 과정이 들어있기 때문에 두 구역에 배치된 적의 수 합이 $W$보다 작은 경우에만 가능합니다. 정리하자면

\[ \begin{align}
& a_{i+1} \leftarrow \min(b_i+1, c_i+1) \\
& \textbf{if }\ e_{1,i}+e_{2,i} \le W \\
& \qquad a_{i+1} \leftarrow \min(a_{i+1}, a_i+1) \\
& \textbf{if }\ i > 0 \ \textbf{ and }\ e_{1,i-1} + e_{1,i} \le W \ \textbf{ and }\ e_{2,i-1} + e_{2,i} \le W \\
& \qquad a_{i+1} \leftarrow \min(a_{i+1}, a_{i-1}+2)
\end{align} \]

여기서 $e_{i,j}$는 $i$행 $j$열에 배치된 적의 수입니다. 한편 1행은 $i+1$열까지 채우고 2행은 $i$열까지 채우는 방법은

  1. 1행과 2행 모두 $i$열까지 채우고 1행 $i+1$열에 특수소대 하나를 채움
  2. 1행은 $i-1$열, 2행은 $i$열까지 채우고 1행 $i$열과 1행 $i+1$열에 특수소대 하나를 채움

따라서

\[ \begin{align}
& b_{i+1} \leftarrow a_{i+1}+1 \\
& \textbf{if }\ e_{1,i}+e_{1,i+1} \le W \\
& \qquad b_{i+1} \leftarrow \min(b_{i+1}, c_i+1)
\end{align} \]

마지막으로 1행은 $i$열까지 채우고 2행은 $i+1$열까지 채우는 방법은

  1. 1행과 2행 모두 $i$열까지 채우고 2행 $i+1$열에 특수소대 하나를 채움
  2. 1행은 $i$열, 2행은 $i-1$열까지 채우고 2행 $i$열과 2행 $i+1$열에 특수소대 하나를 채움

따라서

\[ \begin{align}
& c_{i+1} \leftarrow a_{i+1}+1 \\
& \textbf{if }\ e_{2,i}+e_{2,i+1} \le W \\
& \qquad c_{i+1} \leftarrow \min(c_{i+1}, b_i+1)
\end{align} \]

점화식을 구한 걸로 끝이 아니라 초기 조건도 구해야죠. $a_0$는 1행과 2행 모두 -1열까지 채우라는 의미인데… 채울 필요가 없으므로 0입니다. $b_0$과 $c_0$은 둘 다 1이고요. 최종 정답은 $a_N$입니다.

이제 다시 원형으로 돌아옵시다. 앞에서 푼 선형 문제는 1번 구역과 $N$번 구역에 걸쳐 특수소대를 채우지 않고 $N+1$번 구역과 $2N$번 구역에 걸쳐 특수소대를 채우지 않는 경우와 동일합니다. 만약 1번 구역과 $N$번 구역에 걸쳐 특수소대를 채우고 $N+1$번 구역과 $2N$번 구역에 걸쳐 특수소대를 채우지 않으면 초기 조건이 달라져야 합니다. 이때는 $N\times2$ 직사각형 건물에서 1행 0열과 1행 $N-1$행이 날아갔다고 생각하면 됩니다. 그럼 $a_1$은 1, $b_1$은 2, $c_1$은 $e_{2,0}+e_{2,1}\le W$이면 1, 아니면 2가 초기 조건이 되고, 최종 정답은 $c_{N-1}+1$입니다. 마지막에 1을 더하는 이유는 1행 0열과 1행 $N-1$행에 배치된 특수소대가 있기 때문입니다.

1번 구역과 $N$번 구역에 걸쳐 특수소대를 채우지 않고 $N+1$번 구역과 $2N$번 구역에 걸쳐 특수소대를 채우면 위와 정확히 반대 상황이고, 둘 다 채우면 $a_1$은 0, $b_1$과 $c_1$은 둘 다 1이고 최종 정답은 $a_{N-1}+2$입니다.

코드가 많이 복잡하고 깁니다….