temp   7년 전

부분합을 구해서 처리하면될거같은데 최대가 20만이다보니..

모든 부분합을 구하기가 시간상 오버가 나네요..

힌트 부탁드립니다.

어떤방법을써야 모든 연속된 부분합을 구할수있을까요?

yukariko   7년 전

부분합을 구한 다음,

각 위치에 대해서 순차적으로 방문하면서, 처음부터 현재 위치까지의 부분합 중에 K를 만족하는 부분합의 개수를 구하면 됩니다.

부분합을 구하는대에는 O(N)이 필요하고, 처음부터 현재 위치까지의 부분합을 보는것도 O(N)이라 O(N^2)이 될 수 있지만,

처음부터 현재 위치까지의 부분합 중, 나에게 필요한것은 K - sum 하나 라는 사실을 이용하면

이 숫자를 갖는 부분합의 개수를 로그시간에 찾을 수 있습니다.

따라서 O(NlgN) 으로 답을 구할 수 있게 됩니다.

mic1021   7년 전

제 개인적인 생각입니다만 전처리로 a[i]=i번 수까지의 합을 구합니다. a[1]~a[i-1]을 소트한 다음에 a[i]-a[mid]<k이면 right=mid-1 a[i]-a[mid]>k이면 left=mid+1로 해서 a[i]-a[mid]==k인 지점을 찾습니다. mid 근방도 조사해야 겠지요. 이런식으로 i를 2부터 n까지 돌리면 nlogn만에 찾을 수 있을 것 같습니다.

yukariko   7년 전

@mic1021 a[1] - a[i-1]까지 소트가 O(NlgN)이므로 소트를 사용한다면 N번 반복할때 O(N^2lgN)이 될 수 있을것 같습니다.

mic1021   7년 전

Aㅏ  소트가 lgn인줄 알았네요 하하하

댓글을 작성하려면 로그인해야 합니다.