백준 문제 풀이 - 부분합 1806번

📜 문제 이해하기

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

💡 문제 재정의

수열의 합이 S 이상이 되는 가장 짧은 길이를 구하라.

✏️ 계획 수립

Two Pointer 기법을 쓰면 O(N)안에 문제를 해결할 수 있다.
start와 end를 0번째 인덱스에서 시작하여 만약 start와 end 사이의 값의 합이 S 이상이라면 가장 짧은 길이인지 확인한다. 그 후 S 아래가 될때까지 start를 늘리면서 부분 합을 구한다. 이 작업을 start가 end와 같아질때까지 수행하고 가장 짧은 길이를 출력하면 된다.

💻 계획 수행

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, S, sum = 0, start = 0, end = 0, min_length = 100001;
    cin >> N >> S;
    vector<int> num(N+1);

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

    while (true) {
        if (sum >= S) {
            if (end - start < min_length) min_length = end - start;
            sum -= num[start];
            start += 1;
        }
        else {
            sum += num[end];
            if (end < N) end += 1;
            else {
                sum -= num[start];
                start += 1;
            }
        }
        if (start >= end) break;
    }
    min_length = min_length == 100001 ? 0 : min_length;
    cout << min_length;
    return 0;
}

🤔 회고

이 문제를 처음엔 브루트포스로 풀었으나 해당 알고리즘은 O(N²)이라 시간초과가 발생했다. 두 포인터 알고리즘으로 문제를 해결해야 O(N)안에 문제가 해결되기에 브루트포스를 사용하면 안된다. 아래 링크는 두 포인터 알고리즘에 대한 설명이다.
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md