[1806번] 부분합

문제 출처 :

https://www.acmicpc.net/problem/1806

알고리즘 분석 :

문제 해결에 필요한 사항

1. Prefix Sum :: http://www.crocus.co.kr/259

2. 투 포인터

Prefix Sum에 대한 개념을 알고(부분 합, 구간 합)이를 이용하여 투 포인터로 문제를 해결하면 간단히 해결되는 문제이다.

pSum의 의미는 고등학교 시절에 배우는 수열의 합 부분에서 S를 의미한다.

즉, S[3] = a1 + a2 + a3를 의미하고 S[10] = a1 + a2 + ... + a9 + a10을 의미하며

S[10] - S[3]은 a4 + a5 + a6 + a7 + a8 + a9인 4~9사이의 부분합을 나타내어준다.  

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
#define MAX_N 100001
using namespace std;
 
int arr[MAX_N];
int pSum[MAX_N];
 
int main()
{
    int n, s, minLen = MAX_N, len = 0;
    int p1 = 1, p2 = 1;
 
    scanf("%d %d", &n, &s);
 
    // pSum은 구간 1~i까지의 합을 나타내준다.
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
 
        pSum[i] = pSum[i - 1] + arr[i];
    }
 
    // p1과 p2가 같고, p1이 n에 도달한 경우가 아닌 경우에 while
    while (!(n == p1 && p1 == p2))
    {
        // p1~p2까지의 합이 s보다 크거나 같으면
        if (pSum[p2] - pSum[p1-1] >= s)
        {
            // 길이를 구해주고 최소 길이를 구해준다.
            len = p2 - p1 + 1;
            if (minLen > len)
                minLen = len;
 
            p1++;
        }
 
        // p1~p2까지의 합이 s보다 작으면
        else if (pSum[p2] - pSum[p1 - 1] < s)
        {
            // p2가 아직 끝지점에 도달하지 않았다면 p2++를, 
            // 그 외에는 p1++를 한다.
            if (p2 < n)
                p2++;
            else
                p1++;
        }
 
    }
 
    // 정답 출력
    if (minLen == MAX_N)
        cout << "0";
    else
        cout << minLen;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>