[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을 출력하면 된다.

 

---

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    int n, s;
    cin >> n >> s;

    vector<int> v(n);

    for (int i=0; i<n; i++)
        cin >> v[i];

    int left = 0, right = 0, sum = 0, length = n+1;

    while (right < n) {
        sum += v[right];
        right ++;

        while (sum >= s) {
            length = min(length, right-left);
            sum -= v[left];
            left ++;
        }
    }
    
    if (length == n+1)
        length = 0;

    cout << length;

    return 0;
}

 

풀이

1. n과 s를 입력받고, 수열을 입력받는다.

2. left 포인터와 right 포인터 모두 오른쪽으로 향하며 탐색을 하기 위해 0으로 초기화하고, 현재 요소의 합을 나타내는 변수 sum을 0으로 초기화 하고, 최소 길이를 저장할 length를 n+1로 초기화하여 최종 결과가 없을 경우를 대비해준다.

3. right 포인터를 오른쪽으로 이동하며 배열 v의 값을 sum에 더한다.

4. sum이 s 이상이 되는 동안, 길이(right - left)가 최소 길이인지 확인하고 업데이트하고, sum에서 v[left] 값을 빼며 left 포인터를 오른쪽으로 이동킨다.

5. length가 초기값 그대로면 합이 만들어지는 것이 불가능한 것이므로 0으로 설정한다.

6. 최종 결과를 출력한다.

 

---

고찰

처음엔 부분합이 무조건 2개 이상의 요소의 합이라고 생각하였는데, 문제를 해결하다 보니 하나의 요소만으로 s이상이 될 수 있다는 것을 알게 되었다. 이 점을 갑자기 코드에 도입하려고 하니 오류가 많이 생겼고, while문 안의 로직을 기존과 다르게 많이 바꾸었더니 문제를 해결할 수 있었다.