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

 

🔗 문제 링크 : https://www.acmicpc.net/problem/1806

 

---

 

문제

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

 

 

 

 

 

입출력 예시

입력

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

 

 

출력

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

 

 

 

입출력 예시

 

 

 

---

 

풀이 

해당 문제는 투포인터를 이용해 해결하였다.

• 현재 부분 합이 S보다 작으면 end를 1 증가 시킨다.
• 현재 부분 합이 S보다 크거나 같으면 수열의 길이를 비교 및 갱신하고, start를 1 증가시킨다.

위 과정을 반복한다.

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

int main() {
    ios_base::sync_with_stdio(0);
    int answer = 0x7fffffff;
    int N, S;
    cin >> N >> S;

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

    int end = 0;
    int sum = nums[0];
    for (int start = 0; start < N; start++) {
        while(end < N && sum < S) {
            end++;
            if (end != N) sum += nums[end];
        }
        if (end >= N) break;
        answer = min(answer, end - start + 1);
        sum -= nums[start];
    }
    cout << (answer == 0x7fffffff ? 0 : answer);
    return 0;
}

 

 

 

---