백준 1806 부분합 [C++]

 

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

1806번: 부분합

#문제 간단 정리

투 포인터를 활용하는 문제

많이 볼 수 있는 유형이라 많이 접근해봤다면 쉽게 풀 수 있다

#문제 해결 방법

우선 브루트 포스를 사용하면 

시간 초과가 날 것이 자명하기 때문에

 

값보다 작다면 end포인터를 ++ 하면서 길이를 늘리고

값보다 크다면 start 포인터를 -- 하면서 최소 길이를 확인합니다.

 

이는 가장 '짧은' 연속 부분합 길이를 찾는다고 문제에 나와있기 때문에

투 포인터를 사용해 조절해가며 길이를 찾는다는 아이디어를 생각 할 수 있습니다.

#전체 코드

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }

    int end = 0, start = 0,sum = 0;
    int minlength = INT_MAX;

    while (end < N) {

        if (sum < M) {
            sum += nums[end++];
        }
        while(sum >= M) {
            minlength = min(minlength, end - start);
            sum -= nums[start++];

        }
    }

    if (minlength == INT_MAX) minlength = 0;

    cout << minlength << '\n';
}