백준 온라인 저지 (BOJ) 1806 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include<stdio.h> #pragma warning(disable:4996) #pragma warning(disable:6031) int arr[100001]; int min(int a, int b) {     return a < b ? a : b; } int main() {     int n, s, len = 100001, start = 1, end = 1;     long long sum = 0;     scanf("%d%d", &n, &s);     for (int i = 1; i <= n; i++)         scanf("%d", &arr[i]);     sum = arr[1];     while (1) {         if (sum < s && end == n)break;         if (sum >= s) {             len = min(len, end - start + 1);             sum -= arr[start++];         }         else {             sum += arr[++end];         }     }     printf("%d\n", len == 100001 ? 0 : len);     return 0; } Colored by Color Scripter

cs

투 포인터를 이용해서 풀 수 있다.