[백준 1806번] 부분합 (C++)

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

1806번: 부분합

---

부분합 문제는 투 포인터를 이용하여 해결할 수 있습니다. 

 

구간합의 시작점과 끝점 그리고 시작점과 끝점까지의 합을 저장하는 변수를 이용하여 해결할 수 있습니다. 

백준 사이트의 테스트케이스를 예로 들어보겠습니다. 

0	1	2	3	4	5	6	7	8	9
5	1	3	5	10	7	4	9	2	8

 

먼저, st = 0일때, sum >= S를 만족하는 en을 찾습니다. (단, st는 시작점, en는 끝점, sum은 구간합을 나타냅니다)

st = 0, en = 4일 때, S = 24입니다. 따라서 m = en - st + 1인 5가 됩니다. (단, m은 sum >= S인 구간의 최소 길이)

 

st = 1일 때는, sum - seq[0] >= S이므로, st = 1, en = 4, m = 4, sum = 19가 됩니다. (단, seq[i]는 수열의 i번째 수)

st = 2일 때도, sum - seq[1] >= S이므로, st = 2, en = 4, m = 3, sum = 18이 됩니다.

st = 3일 때도, sum - seq[2] >= S이므로, st = 3, en = 4, m = 2, sum = 15가 됩니다.

st = 4일 때는, sum - seq[3] < S이므로, S보다 크거나 작을 때까지 en을 늘려나가야 됩니다. 따라서 st = 4, en = 5, m = 2, sum = 17이 됩니다. 

 

이와 같은 방식으로 st, en이 n보다 작거나 같을 때까지만 반복하면 됩니다. 

 

⚠️ 단, S를 만드는 부분합이 존재하지 않는 경우, 0을 출력하도록 해야합니다. 

 

아래는 전체 코드입니다. 

 

#include <bits/stdc++.h>
using namespace std;

int seq[100010];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, s; cin >> n >> s;
    for(int i = 0; i < n; i++) cin >> seq[i];

    int st = 0, en = 0, sum = seq[0];   // st는 구간의 시작점, en은 끝점, sum은 구간합
    while(sum < s) sum += seq[++en];    // st가 0일 때, sum >= S를 만족하는 en를 찾음
    int m = en - st + 1;    // m은 sum >= S인 구간인 최소 길이

    if(en >= n){    // S를 만드는 부분합이 존재하지 않을 경우
        cout << 0 << "\n";
    }else{
        while(true){
            sum -= seq[st]; st++;   // 시작점 이동
            if(sum < s)   // 구간합이 S보다 크거나 같지 않으면 en을 늘려감
                while(sum < s) sum += seq[++en];

            if(st >= n || en >= n) break;
            m = min(m, en - st + 1);    // 구간의 최소 길이 업데이트
        }
        cout << m << "\n";
    }
}

 

아래는 문제 풀이에 사용된 테스트 케이스입니다.

 

3 100
1 2 3
-> 0

1 100
100
-> 1

2 103
100 3
-> 2