티스토리 뷰

ICPC/2014 인터넷예선

I. Stains

전명우 2014. 11. 11. 12:43

$1 \times 1$ 크기의 격자 $MN$ 개가 $M \times N$ 크기의 직사각형을 이루고 있다. 각 격자에는 얼룩이 묻어있을 수 있다. $3 \times 3$ 크기의 덮개를 써서 모든 얼룩을 덮고자 할 때, 필요한 덮개의 최소 개수를 구하는 문제다.


이 문제에서 중요한 것은 $M$ 제한이 $N$ 제한에 비해 현저히 작다는 점이다.

한 열에 덮개를 배치하는 경우의 수를 생각해보자. 우선 최악의 경우를 고려하기 위해 $M=10$이라 생각하자. 하나의 덮개를 덮개의 가장 윗 행 번호로 표현하자. 같은 행 번호에 여러 덮개가 있으면 항상 비효율적이며, 9번 행과 10번 행으로 표현되는 덮개는 없다. 따라서 $2^8 = 256$가지를 생각할 수 있다.


좀 더 경우의 수를 줄여보자. 10개의 행을 모두 덮는 경우를 제외하고 덮개가 덮는 구간이 서로 겹치면 항상 비효율적임을 알 수 있다. 이처럼 경우를 간추리면 경우의 수는 29가지가 된다. 이제 간추린 경우의 수를 이용해 아래와 같이 Dynamic Programming을 할 수 있다.


D[i][j][k] = 1~i번째 열까지 모든 얼룩을 덮었고, i-1 열에 덮개가 j로 놓여있고, i 열에 덮개가 k로 놓여있을 때 이용한 덮개의 최소 개수


점화식은 아래와 같다.

D[i][j][k] = min(D[i-1][l][j] + C[k])

(단, i-2 열에 덮개가 l 처럼 있고, i-1 열에 덮개가 j 처럼 있고, i 열에 덮개가 k 처럼 있을 때 i열에 있는 모든 얼룩을 덮어야한다.)

여기서, C[k] = k로 덮개를 놓을 때 이용한 덮개의 수이며, l은 임의의 한 덮개 배치다.


덮개 배치의 가능한 경우의 수를 $K = 29$로 나타내면 총 시간복잡도는 $O(NK^3)$이 된다.



'ICPC > 2014 인터넷예선' 카테고리의 다른 글

F. Intersections  (3) 2014.11.11
I. Stains  (0) 2014.11.11
J. Switch Array  (0) 2014.10.08
K. Traffic Jams  (0) 2014.10.08
G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
댓글
댓글쓰기 폼