[BOJ/백준 1806][C++] 부분합

문제

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

백준 1806

 

문제 내용

합이 S이상이 되는 연속되는 수열의 부분합 중에, 가장 짧은 길이를 출력하면 된다.

 

문제 풀이

투포인터 방식으로 문제를 해결하면 쉽게 해결할 수 있다.

st와 en 포인터를 두고, st~en까지의 합이 S보다 작으면 en을 증가시키고, 그렇지 않으면 st를 증가시키면 된다.

인덱스(st, en)가 바뀌면 total 값도 조정을 해주어야 한다.

 

st가 en을 앞서는 순간이 오거나, st나 en이 n이 되면 break를 걸어 불필요한 연산을 줄이고 인덱스 에러를 막아야 한다.

 

또한 합이 S이상인 부분합을 만들지 못하면 0을 출력해야 한다는 것을 놓치면 안 된다.

 

코드

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

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

    int mmin = 100005;
    int total = arr[0];
    int st = 0, en = 0;
    while (true) {
        if (total < s) { // en 증가
            en++;
            if (en == n)
                break;
            total += arr[en];
        } else {
            mmin = min(mmin, en - st + 1); // 길이 업데이트
            total -= arr[st];
            st++; // st 증가
        }
    }

    cout << ((mmin == 100005) ? 0 : mmin);
}