[BOJ] 백준 1806 부분합 c++ (투포인터)

문제 출처 : https://www.acmicpc.net/problem/1806

1806번: 부분합

---

풀이

연속된 수의 부분합 중 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이다.

 

단순하게 합을 구한다고 해서 정렬이나 priority_queue를 쓰면 안된다. 연속된 수의 부분합이기 때문이다.

그렇다고 브루트포스로 구현하면 시간초과가 발생한다. 어떻게 해야 할까?

바로 투포인터 알고리즘을 사용하면 된다.

---

투포인터 알고리즘

이름 그대로 배열을 이동하는 포인터가 두개라고 생각하면 된다.

두 포인터를 이동시키며 그 사이의 합을 구할 것이다. (연속된 수의 부분합)

이 합이 S보다 크고 가장 짧은 것이 정답이다.

1. 처음 두 포인터 start, end를 선언하고 가장 첫 부분(1)에 위치시킨다.
2. 두 포인터가 둘다 1에 있으므로 초기 합(sum)은 arr[1]이다.
3. 반복문 범위는 start가 end를 넘지 않고, end가 N를 넘지 않게 설정한다.
4. 합이 S보다 크면 그동안의 최소치와 비교해 ans에 저장한다.
5. 만약 합이 S보다 작으면 두 포인터의 범위를 넓혀야 한다. 따라서 end 포인터를 1증가시키고 증가시킨 부분을 더한다.
6. 합이 S보다 큰 경우 최소치를 검사하기 위해 start 포인터를 1 증가시키고 좁힌 부분을 뺀다.

이렇게 범위를 이동시키면서 정답을 구할 수 있다.

// arr은 수가 담겨있는 배열
int start = 1, end = 1;
int sum = arr[1];
int ans = INT_MAX;
while(start <= end && end <= N){
    if(sum >= S) ans = min(ans, end-start+1);
    if(sum < S){
        end++;
        sum += arr[end]; 
    }else{
        sum -= arr[start];
        start++;
    }
}

---

코드

#include <bits/stdc++.h>

using namespace std;

int arr[100000+1];

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, S;
    cin >> N >> S;
    for(int i = 1; i <= N; i++)
        cin >> arr[i];

    int start = 1, end = 1;
    int sum = arr[1];
    int ans = INT_MAX;
    while(start <= end && end <= N){
        if(sum >= S) ans = min(ans, end-start+1);
        if(sum < S){
            end++;
            sum += arr[end]; 
        }else{
            sum -= arr[start];
            start++;
        }
    }
    if(ans == INT_MAX) cout << 0 << '\n';
    else cout << ans << '\n';
	return 0;
}