BOJ 30027

문제 링크

 

코드

http://boj.kr/942a617eb273499fa12250bd1e91dfb5

 

2023 충남대학교 SW-IT Contest Division 1 K

 

난이도 : P3

 

Elapse Time : 70min

 

어떤 위치가 며칠 후에 꽃이 필지 구해보면 그 위치에서 초기에 꽃을 심은 있는 위치들과의 거리 중 최솟값이 된다. 모든 위치에서의 값 중 최댓값을 구하는 것이 이 문제의 요구사항이다. 이 문제에서 가장 눈이 간 것은 $M$에 비해 $N$의 범위가 작다는 것이다. 처음에는 모든 위치 중 어떻게 위치의 후보를 줄일지 생각했다. 하지만 $K$개의 점들의 위치 관계가 항상 달라지는데 이를 일반화하기는 쉽지 않아 보였다. 두 번째로 한 생각은 파라메트릭 서치가 사용 가능한지이다. 그러나 방법이 쉽게 떠오르지 않아 다른 방법을 생각해 보기로 했다. $O(MK)$는 안되지만 $O(NK)$는 충분히 가능한데 이를 활용할 생각을 해보았다. 그러던 중 $(i,j)$와 $(i,j+1)$에서 값을 비교해 보았는데 $(i,j)$보다 왼쪽에 있거나 같은 열에 있는 점에 대해서는 거리가 1 증가하고, 오른쪽에 있는 점에 대해서는 거리가 1 감소하는 것을 확인했다. $M$개의 열을 다 볼 필요 없이 꽃을 심는 점이 있는 열만 봐도 두 열 사이에서의 값은 계산이 가능하다는 것을 알게 되었다. 이제 각 행별로 $K$개의 열에서 값을 계산하는 것이 남았다. $p$번째 행에 대해 값을 구할 때 처음에는 모든 점들이 오른쪽에 있으므로 $dist((p,0),(x,y))$를 기준으로 정렬해 놓고 오른쪽으로 옮길 때마다 왼쪽으로 간 점들은 무시하면 오른쪽에 있는 점과의 거리 중 최솟값을 구할 수 있다. 왼쪽에 있는 점들의 경우 더 간단한데 오른쪽으로 갈 때마다 왼쪽으로 옮겨간 점과 기존에 가장 가깝던 점 중 $(p,\mathrm{INF})$ 과의 거리가 더 작은 점을 선택하면 된다. 이 방법으로 모든 행에서 $K$개의 열에 대해 계산을 완료했고 이를 바탕으로 최댓값을 구해주었더니 맞았다.