BOJ 10076 - 휴가

문제 요약

 

\(N\)개의 도시가 일렬로 있다. 특정 도시에서 시작해, 인접한 도시로 이동하거나 특정 도시의 관광지를 방문하는 행동을 최대 \(d\)번 할 수 있다. 한 도시의 관광지를 여러 번 방문할 수는 없을 때, 방문할 수 있는 관광지의 최대 개수를 구하여라.

 

풀이

방향을 두 번 이상 꺾는 것이 최적이 아님은 쉽게 알 수 있다. 따라서 왼쪽으로 갔다 오른쪽으로 가거나, 오른쪽으로 갔다 왼쪽으로 가는 경우가 있다. 한 경우를 해결하면 남은 하나는 뒤집은 후 똑같이 해결하면 되므로 전자의 경우만 보도록 하자.

\(x \leq st \leq y\)에 대해, \(st - x - y\) 순으로 방문했다고 하자. 이동하는 데에 \(st+y-2x\)만큼이 필요하므로 \([x,y]\) 구간에서 고를 수 있는 도시의 개수는 \(min(y-x+1,d-(st+y-2x))\)이다. 이를 간단히 \(k\)라 하자.

여기서 관찰 하나를 해야 한다: \(x_1 < x_2\)에 대해 \(opty_1 \leq opty_2\)이다.

\(opty\)란 식의 값을 최대화하는 \(y\)이다. 정확한 증명까지는 아니어도, 다음과 같은 사고과정을 통해 이를 확인할 수 있다.

\([x_1, opty_1]\)에서 \(k\)개를 골랐다고 하자. 이 경우, \([x_1, opty_1-1]\)에서 \(k+1\)개를 고른 것보다 큰 값을 가져야 하므로 \([x_1, opty_1-1]\)에서 \(k+1\)번째와 \(k\)번째로 큰 값의 합보다 \(a_{opty_1}\)이 크다고 할 수 있다. 만약 \(opty_{x_1+1}\)이 \(opty_1-1\)이라면, \([x_1+1,opty_1-1]\)에서 \(k+2\)개를 고른 것이 \([x_1+1,opty_1]\)에서 \(k+1\)개를 고른 것보다 커야 한다. 즉, \([x_1+1,opty_1-1]\)에서 \(k+2\)번째와 \(k+1\)번째로 큰 값의 합이 \(a_{opty_1}\)보다 커야 하는데, 이는 모순이다.

따라서 dnc optimization을 적용할 수 있다.

이제 남은 것은 \([l,r]\)에서 가장 큰 \(k\)개의 합을 빨리 구하는 것이다. 이는 PST를 사용하면 간단히 해결할 수 있지만, 나는 다른 방법을 사용하였다.

세그 이분탐색을 이용하자. 좌표압축을 한 후 한 세그에는 해당 값이 구간에 있는지, 한 세그에는 좌표압축을 하지 않은 실제 값을 저장해두면 뒤 \(k\)개에 대한 합을 구할 수 있다.

이 때, 업데이트를 많이 하지 않도록 주의해야 한다. 매번 초기화하고 업데이트하면 최악의 경우 \(O(N^2logN)\)번 정도의 업데이트를 하게 된다. 나는 \(f(s,e,l,r)\)에 대해 함수 호출 시 \([m,l)\) 구간이 업데이트 되어 있도록 구현하였다.

쿼리에 \(O(logN)\), dnc opt가 \(O(NlogN)\)이므로 총 시간복잡도는 \(O(Nlog^2N)\)이다.

나는 \(x=st\)인 경우를 이상하게 예외처리 하다 틀렸다. 사실 dnc 호출 시 \(x\)의 구간을 \([0,st]\)로 주기 때문에 고려해주지 않아도 된다.