[Algorithm] Parametric Search

7이 아니고 9 임.

최소한 몇 개의 연속된 값을 ???????? 우리가 주목할 부분

위와 같은 방법은 구간 x가 가능한지 판단할려면 O(n)이 소요된다.

최악의 경우 n번 곱하기 n 이라서 최악의 경우 O(n^2) 의 시간복잡도를 가진다.

N<=100,000 이므로 1초 안에 해결될 수 없다.

그러므로 이 때 Parametric Search를 사용한다.

정답은 정말 처음부터 끝까지 다 해보아야 하나 ? ' 아니~~

3이 될 경우, 그 이후는 반드시 가능하다. 

XXOOOOOOO  의 패턴 있다.

X와 O의 경계를 찾으면 끝난다.

되는 값 중 가장 작은 값 3을 찾는게 우리가 해야 하는 것이다. -> Binary Search로 가능하다.

Start는 무조건 X를 가리키고, End는 무조건 O를 가리킨다.

인덱스를 나누어 보았을 때 중간값이 O일 경우, 그 이후의 구간값의 합일 경우에는 모두 O가 된다.

그러므로 mid 이전의 부분만 이분 탐색해주면 시간복잡도가 개선된다.

시간복잡도 O(nlog(n)) 만큼 걸리게 된다..

n^2 보다 훨씬 좋아진 것을 알 수 있당

<코드>

#include<iostream>

using namespace std;

const int MAX = 100005;

int n;

int S;

int data[MAX];

bool check(int interval){

// 구간의 길이 interval 만큼 정했을 때, 그 합이 S 이상인 경우가 있는가 ? 

// 있으면 TRUE, 아니면 FALSE

int sum = 0;

for(int i=0; i<interval; i++) sum += data[i];

if(sum >= S) return true;

for(int i=0; i<n-interval; i++){

sum = sum - data[i] + data[i+interval];

}

if(sum>=S) return true;

return false;

}

int main(){

scanf("%d %d",&n,&S);

for(int i=0; i<n; i++) scanf("%d",&data[i]);

int start = 1; // start는 무조건 X를 가리킴 

int end = n; // end는 무조건 O를 가리킴 

if(check(1)){

printf("1\n");

return 0;

}

if(!check(n)){

printf("-1\n");

return 0;

}

// 1 2 3 4 5 .... 10 11 12 

//                 X  O  O

while(start+1 < end){

int mid = start + end / 2;

if(check(mid)){

end = mid;

}else{

start = mid;

}

}

printf("%d\n",end);

return 0;

}