백준 1806 - 부분합

1. 문제 정리
  - 10000 이하의 자연수로 이루어진 길이 N의 수열이 주어진다.

  - 수열의 연속된 수들의 부분합 중 그 합이 S 이상이 되는 부분수열 중 길이가 최솟값이 수열의 길이를 출력한다.
 
2. 접근
  - 처음에는 BruteForce로 접근하였으나, 시간초과를 맞았다

  - two point 알고리즘을 이용하여 부분수열의 길이가 최소가 되는 지점을 찾고자 하였다.
 
3. 풀이

//2022.01.12
#include<iostream>
#include<algorithm>
using namespace std;

int n, s;
int a[100000];
int ans = 100000001;

int min(int a, int b){
    if (a < b) return a;
    return b;
}

void solve(){
    int low = 0, high = 0;
    int sum = a[0];

    while (low <= high && high < n)
    {
        if (sum < s)
                sum += a[++high];
        else if (sum == s)
        {
                ans = min(ans, (high - low + 1));
                sum += a[++high];
        }
        else if (sum > s)
        {
                ans = min(ans, (high - low + 1));
                sum -= a[low++];
        }
    }
}

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

    cin >> n >> s;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    solve();
    if(ans == 100000001)cout << 0;
    else cout << ans;
}

  - int ans : 부분수열의 길이의 최솟값을 저장할 변수이다. main 함수에서 값이 변하지 않고 가질 수 있는 최대값보다 1이 큰 값(100000001, S의 최대값+1)이라면 0을, 그렇지 않다면 ans값을 출력하도록 한다.

  - void solve() : two point로 구현하였다. low값이 high 이하이며, high 값이 n보다 작은 동안 동작하고, 부분합이 s 보다 작다면 high에 1을 더하고 부분합에 a[high+1] 값을 더한다. 부분합이 s 보다 크다면 low에 1을 더하고 부분합에 a[low]값을 빼준다.

 위 과정에서 문제의 해답 조건인 "부분합 >= s"가 일치하는 조건문에서는 ans 값의 최솟값을 갱신해준다.

 
4. 소감

 two point 알고리즘은 처음 써봤다. 사실 이전에 따로 공부해본 적도 없고 학부 수업에서 접해본 적도 없었기에 생소하였지만, 개념 자체가 어려운 개념이 아니어서 바로 쉽게 배울 수 있었다.

 백준 PS 강의도 듣고, 학부 알고리즘 수업도 들었지만 아직 모르는 알고리즘이 많고, 그것들을 공부함으로 더 다양한 문제를 더 다양한 풀이 방식으로 해결할 수 있기에 이후에 기회가 된다면 알고리즘 카테고리를 따로 만들어 공부한 내용을 정리해보는 것도 생각하고 있다.