BOJ 14870: 조개 줍기

Link

• https://www.acmicpc.net/problem/14870

• KOI 2017 고등부 4번

Tag

• dp

• Segment Tree

Time Complexity

• $O(N^2lgN)$

 $N \times N$ 격자에 조개가 있다. 각 점에서 $(1,1)$로 최단거리로 이동하면서 조개를 주울 수 있는 최댓값을 구해야 한다. 한번만 구하는게 아니라, $N$개의 쿼리가 주어져서 한 지점의 조개 개수가 1 증가하거나 감소한다. 이때 모든 지역에서 주울 수 있는 조개 개수의 최댓값의 합을 출력해야 한다.

 먼저 $(1,1)$로 이동하는것을 $(1,1)$ 에서 각 지점으로 이동하는 것으로 바꾸어 생각하자. 그러고 나면 쿼리가 없는경우 아주 간단한 dp로 풀리는 것을 알 수 있다. 이제 쿼리를 어떻게 처리하느냐가 문제다.

 어떤 지점 $(r,c)$ 의 조개 개수가 변화했다고 하자. 그러면 이 지점에 직접적으로 영향을 받아 dp값이 바뀔 수 있는 지점은 $(r+1,c)$ 또는 $(r,c+1)$ 이다. 따라서 어떤 지점의 조개 개수가 변화했을 때, dp값이 바뀌는 부분을 행 단위로 잘라서 보면 시작점과 끝점이 단조 증가하는 형태이다.

 이제 투 포인터 느낌으로 dp값이 바뀌는 부분의 구간을 $O(N)$에 구해 줄 수 있겠다. 이제 이 dp값을 변화시키는게 문제인데, Range-update Point-query 세그먼트 트리를 N개 만들어 주면 업데이트도 $O(NlgN)$에 할 수 있다. 총 문제는 $O(N^2lgN)$에 해결 되겠다.

 

Code