[백준] 1806 - 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

 투포인터 문제다. 특별히 주의해야할 사항은 없고 left, right 두 인덱스를 이동시키면서 부분의 합을 S이상을 넘기면서, 가장 짧은 길이를 갱신해나가면 된다. 시간 복잡도는 O(N)

#include<iostream>
#include<stdio.h>
 
using namespace std;
 
unsigned int arr[100001];
 
int main() {
    int n, m;

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

    for (int i = 0; i < n; i++) {
        scanf("%u", &(arr[i]));
    }

    unsigned int result = 0xFFFFFFFF;
    unsigned int len = 0;
    
    int left = 0; 
    int right = 0;
    unsigned int sum = arr[0];
 
    while (left <= right && right < n) {
 
        if (sum < m) {
            if (right < n) {
                right += 1;
                sum += arr[right];
            }
        }
        else if (sum >= m) {
            len = right - left + 1;
            if (result > len) {
                result = len;
            }
 
            if (left <= right) {
                sum -= arr[left];
                left++;
            }
        }
    }
 
    if (result == 0xFFFFFFFF) {
        printf("0\n");
    }
    else {
        printf("%u\n", result);
    }
 
}