알고리즘 study -15-

<매개 변수 탐색>

-> Binary Search를 이용하여 문제를 해결하는 테크닉

---

ex> n개의 숫자와 s가 주어질 때, 몇 개의 연속된 값을 합해야 그 합이 s 이상이 되는가? (단, 1 <= n <= 100,000)

-->> Idea : 처음부터 끝까지 다 해봐야 하는 것인가?

ex> 9 14 / 2 1 8 1 3 7 2 6 3
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
구간 1 : x
구간 2 : x
구간 3 : 7 2 6 에서 합이 14이상이므로 구간 3부터 가능

---

구간은 1 부터 최악의 경우 n까지 존재
(구간 x : 연속된 x개의 값)

---

구간 m에서 그 합이 s 이상이 되는 경우 m보다 큰 구간에서도 모두 가능
(이 패턴을 찾는 것이 중요)

--> 이제 m 보다 큰 구간은 고려 대상이 아님

---

1~n 구간 값을 오름차순으로 나열한 배열에서 이진탐색 실행

start : 안되는 구간
end : 되는 구간

---

mid = (start + end)/2
구간mid가 되는 구간이면 end = mid / 안되는 구간이면 start = mid

---

--> start 와 end가 붙어 있으면 안 되는 구간과 되는 구간의 경계!
이때 end 구간이 정답

---

#include <stdio.h>

const int MAX = 100010;
int n, s;

int data[MAX];

bool check(int interval){
 // 구간 길이 interval 만큼 그 합이 S 이상인 경우가 있는가?
 
 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)){  // n이 안되면 전 구간 불가능
   printf("-1\n");
   return 0;
 }
 
 
 // 여기까지 오면 start가 가리키는 1은 x,  end 가 가리키는
 // n은 o 이다
 

---