[백준 1806번] 부분합 (C++)

문제링크 : https://www.acmicpc.net/problem/1806

1806번: 부분합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, S;
    cin >> N >> S;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    int s = 0, e = 0;
    int sum = arr[s];
    int result = MAX;

    while(e<N) //배열 끝까지 탐색
    {
        if(sum < S) sum+=arr[++e]; //뒤에 값 이동
        else 
        {
            result = min(result, e-s+1); //길이 저장
            sum-=arr[s++]; //앞에 값 이동
        }
    }
    cout << (result == MAX ? 0 : result);
    return 0;
}

두 포인터를 사용해 푸는 누적합 문제이다.

처음에 포인터를 둘다 0, 0으로 시작하여 뒷 포인터 부터 움직이면서 합을 체크해주면 된다.

 

먼저 현재 합이 S미만 이라면 현재 합에 다음 위치 값을 더해준다.

현재 합이 S이상이라면 최소 길이를 저장해주는 동시에 다른 범위 탐색을 위해서 앞 포인터를 한 칸 뒤로 옮겨준다.

 

이를 반복하며 현재 합이 S이상일 때 최소 길이를 추려준다.