BOJ 1806 - 부분합 문제풀이

문제를 읽고 이해하기

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

재정의와 추상화

이 문제는 투 포인터 알고리즘(Two Pointers Algorithm)을 이용한 대표적인 문제다. 이 문제를 처음 시도할 때 아무것도 모른 채 접근했기 때문에 너무 힘들었는데, 역시 30분이 걸려도 갈피를 못 잡겠으면 구글링이 답이라는 것을 깨달았다..

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window)

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

위 문서를 읽고 나면 쉽게 풀 수 있을 것이다. 다른 점이라면, 문제에서 그 합이 S 이상이 되는 것들 중, 가장 짧은 것의 길이를 구한다는 점이다. 이걸 깨닫지 못해서 6번이나 재시도했던 경험이 있다..ㅠㅠ

코드 작성

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

int arr[100000];
int shortest = INT_MAX;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> arr[i];

    int start = 0, end = 0, result = 0;
    while (true) {
        if (result >= s) { result -= arr[start++]; }
        else if (end == n) break;
        else result += arr[end++];

        if (result >= s) shortest = min(end - start, shortest);
    }
    cout << ((shortest == INT_MAX) ? 0 : shortest);
    return 0;
}