백준 1806: 부분합

문제 요약

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

문제 분류

• 누적 합
• 두 포인터

문제 풀이

우선 누적 합 배열 S[]를 선언하여 각 수열의 합을 누적시킨다. 이후 두 포인터알고리즘을 적용시키면 된다.

우선 순회할 두 변수는 i와 j로 둔다. 나는 i~j까지의 합을 비교하여 그 최소 크기를 답으로 출력할 것이다. 그러므로 i는 0으로, j는 1로 초기화해준다.

i~j까지의 누적 합이 m보다 작으면 j를 증가시키면 된다.
그렇지 않으면, 결과 값(res)에 j - i 와 자신 중 더 작은 값으로 대입시키고 i를 증가시킨다. 수열은 모두 자연수로 이루어져 있으므로 i~j의 누적합은 이전 값보다 작아져 있을 것이다. 그리고 이 값과 m을 다시 비교하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m, S[100001];

int main() {
    int in, res = 0, i, j;
    cin >> n >> m;
    for (i = 0; i < n; i++) {
        scanf("%d", &in);
        S[i + 1] = S[i] + in;
    }
    for (i = 0, j = j; j <= n;) {
        if (S[j] - S[i] < m) j++;
        else {
            if (res == 0 || res > j - i) res = j - i;
            i++;
        }
    }
    cout << res;

    return 0;
}