SCPC 2016 본선 3번 풀이. 폭격

문제 설명

2차원 격자칸 형태의 적국에 폭격을 하려고 한다.

격자칸의 가로 크기는 N, 세로 크기는 M 이다.

좌표는 가장 왼쪽 위 칸을 (1 , 1)로, 가장 오른쪽 아래 칸을 (M,N)으로 표현한다.

각 격자칸에 최대 하나의 목표물이 있으며, 전체 목표물의 개수는 P 로 주어진다.

각 폭격기는 3X3크기의 영역에 있는 목표물을 모두 파괴할 수 있으며, 그 영역에 두 개 이상의 목표물이 있어야 출격이 가능하다고 한다.

적국의 목표물 위치가 주어졌을 때 모든 목표물을 파괴할 수 있는 최소의 폭격기 수를 계산하라.

두 개 이상의 폭격기가 하나의 목표를 파괴하는 것도 가능하다.

아래 그림에서 왼쪽의 경우는 어떤 경우에도 한 폭격기는 하나의 목표만 파괴할 수 있어서 폭격이 불가능하다.

오른쪽의 경우는 두 대의 폭격기가 출동하면 모두 파괴가 가능하다.

제약 조건: 3 <= M <= 10, 3 <= N <= 100,000, 2 <= P <= 1,000

실행 조건: 테스트 케이스 16개에 대한 실행 시간 총합이 1초 이내. 메모리 256MB 이내.

부분문제 1, 2 풀이

KOI 두부 모판 문제처럼 하되 3진수 DP를 하면 풀린다.

상태 정의는 "DP[n][i][trimask] = (1열부터 n-1열까지, 그리고 n열 1행부터 n열 i행까지 영역 내에 완전히 포함되는 3X3 폭격기만 전부 사용할 때, 1열부터 n-3열까지, 그리고 n-2열 1행부터 n-2열 i행에 들어있는 목표물은 전부 폭격하고, 나머지 부분은 trimask에 의해 지정되는 영역에 들어있는 목표물만 전부 폭격하기 위한 3X3 폭격기의 최소 사용 대수. 만약 조건을 만족하면서 해당 영역 내의 목표물을 전부 폭격하는 방법이 존재하지 않는 경우 무한대)"이다.

(trimask: 각 행에 대해 3진수로 커버 여부를 나타낸 마스크. bitmask의 3진수 버전)

점화식은 어떻게 세울까? n-2열 i-2행부터 n열 i행에 이르는 3X3 영역을 폭격할 수 있는지부터 생각해보자. 만약 폭격할 수 없다면, 해당 위치에 목표물이 존재하는 경우 INF, 존재하지 않는다면 해당 위치를 제외한 영역의 최적해인 DP[n][i-1][trimask']와 같다.

하지만 폭격할 수 있다면 어떤가? 해당 영역에 대한 폭격을 포함하는 해당 부분문제의 최적해를 생각해보자. 이 폭격 P를 들어내면 해당 3X3 영역의 n열 i행을 제외한 8개의 칸은 전혀 폭격되지 않거나, 일부가 폭격되고 있을 것이다. 이 형태는 해당 영역만 커버하는 trimask'에 대해 최적해이다. 왜냐면 그보다 더 좋은 해가 있다면 그 해에 P를 얹어 더 나은 최적해를 만들어낼 수 있어 모순이기 때문이다.

모두 나열해보면 34가지의 조합이 존재하므로 꽤나 많다고 생각될 수 있지만, 정말 34개의 케이스를 모두 고려해야 하는지 다시 생각해보자. 현재 상태 정의상 위에 나열한 세 가지 경우는 그룹 내부에서는 각각 사용 가능한 폭격기 세트가 동일한데, 사용 가능한 폭격기 세트가 동일할 때 목표물 집합 A와 B가 A⊆B를 만족하면 항상 (A를 커버하는 최소 비용) ≤ (B를 커버하는 최소 비용)이다. 왜냐면 B를 커버하는 폭격 위치 조합은 항상 A도 커버하기 때문이다. 이런 관점에서 생각해보면, 각 그룹에서 고려할 값은 가장 커버리지가 적은 것 하나씩뿐이다. 따라서 34가지가 아니라 3가지만 고려하면 된다.

그러면 연산횟수가 (열의 개수) x (행의 개수) x 3^{(행의 개수)} x 3으로 줄어든다. 하지만 열이 100,000개나 있으므로 이를 줄여야 한다. 다행히도 목표물이 기껏해야 1,000개 있으므로 열의 개수를 2,000개로 줄일 수 있다. 어떻게 할까? 목표물과 목표물 사이에 빈 열이 두 개 이상 있다면 두 영역은 서로 폭격기를 공유할 수 없다. 따라서 독립된 문제로 볼 수 있다. 그러므로 독립된 문제가 아니려면 목표물이 있는 두 열은 그 사이에 빈 열을 많아야 하나밖에 둘 수 없으므로, 실제로 고려해야 할 열은 기껏해야 목표물 수의 2배인 2,000개 뿐이다(더 정확히 말하면, 2,001개).

이렇게 하면 부분문제 1(2 <= P <= 20)과 2(3 <= M <= 6)는 해결된다.

부분문제 3 풀이

정말 더러운 DP 최적화를 해야 한다. 이 문제의 경우 데이터 특성이 희소(sparse)하다. 즉 가로로 길게 늘어져 있으려면 한 열에 폭격기가 많이 있을 수 없다. 따라서 모든 상태를 계산할 필요 없이 줄어든 폭만큼만 상태를 계산하면서 넘어가도 문제가 없다. 대신 그 다음 번에 폭이 도로 늘어나도 계산을 이어할 수 있도록 충분한 정보를 주어야 한다.

구체적으로 얘기하면, 매 열마다 폭탄이 있는 가장 위쪽 위치와 가장 아래쪽 위치가 있다. 이를 U, D라 하자. [U, D] 바깥에 폭탄이 없는 열이 3번 연속된다면, 해당 3열 내에서 [U, D] 바깥에 걸치지 않는 3x3 위치만 폭격하는 최적해가 존재한다. 왜냐면 해당 위치에 폭격했다고 하면 이들을 안쪽으로 집어넣어도 여전히 커버리지를 손해 보지 않으면서 폭격이 가능하기 때문이다. [물론 집어넣을 수 있으려면 D은 U+2 이상이어야 한다. 하지만 실질적으로 별 문제는 없다. 높이가 최소 3이라는 것은 계산복잡도에 큰 문제를 일으키지 않기 때문이다].

다음 열로 가서 폭이 늘어나거나 변한 경우에는 적절히 interpolation을 하면 된다.

이렇게 하면 아슬아슬하게 1초 내에 통과할 수 있다.

보충 설명

* 점화식을 세울 때 반드시 해당 영역 내에 3x3 폭격기가 모두 제한되도록 해야 한다. 만약 그 밖으로 삐져나가는 것까지 허용하게 되면 점화식을 세우기가 무척 힘들어진다.