BOJ 2855 : 흥미로운 수열

문제 링크 : https://www.acmicpc.net/problem/2855

 

흥미로운 수열은 길이가 항상 2K 꼴의 짝수다.

앞 K 개와 뒷 K 개 수의 합이 둘 다 S 이하면 흥미로운 수열이다.

길이 N짜리 수열과 S가 주어졌을 때, 연속부분수열 중 가장 긴 흥미로운 수열의 길이를 출력하면 된다.

 

딱 봐도 이진탐색인데, 정당성이 없었다.

A[1] ~ A[K] // A[K+1] ~ A[2K] 가 흥미로운 수열이 아니었다고 해도

A[1] ~ A[K+1] // A[K+2] ~ A[2K+2] 가 흥미로운 수열이 될 수 있기 때문이다.

(A[K+1] 이 엄청 큰 수고 A[2K+1] + A[2K+2] 가 엄청 작으면 가능하다)

 

그러다 문득 가운데를 고정해놓으면 이진탐색의 정당성이 부여된다는 것을 깨달았다.

A[2] ~ A[K] // A[K+1] ~ A[2K-1] 가 흥미로운 수열이 아니면

A[1] ~ A[K] // A[K+1] ~ A[2K] 는 흥미로운 수열이 절대로 될 수 없다.

시작점인 A[1] 을 고정하는 것이 아닌, 가운데인 A[K] // A[K+1] 을 고정하니 쉬운 문제가 되었다.

 

각 점들을 다 가운데로 간주하여 이진탐색을 돌려서,

각 점이 가운데가 됐을 때 최대 몇 칸 뻗을 수 있는지를 파악한다. 이게 O(N log N) 걸린다.

 

답을 출력할 때는, 각 칸마다 자신에게 최대로 뻗을 수 있는 칸을 O(log N) 시간에 알아내면 된다.

나는 Segment Tree 를 활용하였다.

 

따라서 출력도 O(N log N) 으로 할 수 있다.