Codeground 부분배열

Codeground 부분배열 https://www.codeground.org/practice/practiceProblemView


N개의 자연수가 담긴 수열중 합이 S보다 크거나 같은 부분수열의 가장 작은 크기를 구하는 문제이다. (N <= 100,000)

처음에는 segment tree인가 하다가 분할탐색이구나 하고 느꼈다가 
이분탐색이구나라고 깨달음을 얻었다.

수열을 누적합으로 바꿔주고 1부터 N까지 for문을 돌리며 1부터 해당 index의 크기만큼의 
부분수열의 합이 S보다 크거나 같은 최소가되는 점을 이분탐색해주면 된다.

시간복잡도는 $O(N*logN)$ 이 된다. 

#include <cstdio> #define min(a,b) ((a)<(b)?(a):(b)) int N, S; int ans; int arr[100001], sum[100001]; void binary(int num){     int l = 1, r = num;          while (l < r){         int mid = (l + r) / 2;         if (sum[num] - sum[mid - 1] > S){             ans = min(ans, num - mid + 1);             l = mid + 1;         }         else if (sum[num] - sum[mid - 1] < S)             r = mid;         else{             ans = min(ans, num - mid + 1);             break;         }     } } int main(){     setbuf(stdout, NULL);       int T;     scanf("%d", &T);          for (int t = 1; t <= T; t++){         ans = 1e9;         scanf("%d%d", &N, &S);         for (int n = 1; n <= N; n++){             scanf("%d", &arr[n]);             if (n == 1)                  sum[n] = arr[n];             else                 sum[n] = arr[n] + sum[n - 1];             if (arr[n] >= S) ans = 1;             if(sum[n] >= S && ans > 1)                  binary(n);         }         printf("#testcase%d\n", t);         printf("%d\n", ans == 1e9 ? 0 : ans);     }     return 0; } Colored by Color Scripter

cs