[BOJ/C++] 1806: 부분합

🏅 Gold 4

✏️ 1차 솔루션

for 문으로 0부터 시작해서 size를 늘려가며 부분합 만들면서 s보다 부분합이 커지는 순간 break

🚨 1차 trouble

이중 for 문이 될 수밖에 없어서 시간복잡도가 O(N^2) 인데다가 모든 조합을 만들어야 하기 때문에 무수한 조합을 검증해야해서 비효율적 ➡️ 다른 알고리즘 필요

✏️ 최종 솔루션

투 포인터 활용
l: 부분합 시작 위치를 가리킬 포인터
h: 끝 위치를 가리킬 포인터
len: 최저 부분합 길이

포인터 h를 0에서 시작해 오른쪽으로 옮겨가며 처음 s 이상이 되는 최저 부분합 크기 찾기
1) 부분합이 s보다 작다면 계속해서 h 는 늘려주면서 누적합에 다음 수열 더해주기
2) 최저 부분합 크기 찾으면 len 갱신해주고 누적합에서 포인터 l 의 수열 값을 빼주고 l 늘려주기
➡️ 일단 최저 부분합 크기 찾으면 s 이상이 되는 한 계속해서 l 의 위치를 오른쪽으로 옮겨주고 s 미만이면 h 의 위치를 옮겨주는 방식 반복
➡️ s 이상이 된다면 기존 값과 비교해 최소값을 저장하기 때문에 h 가 맨 끝자리 도달하거나 s 인 원소를 만나는 한까지 반복하는 과정에서 len 이 다시 늘어나도 최소값 유지 가능

📌 self feedback

투포인터의 풀이 방법이 정해져 있는 것이 아니라 포인터 2개로 시간복잡도를 줄이고 알고리즘을 최적화하는 것이 목표이기 때문에 문제마다 목적에 맞게 유동적으로 활용해야함

✏️ 최종 code

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

using namespace std;

int main() {
    int n, s;
    cin >> n >> s;
    
    vector<int> v;
    for(int i=0;i<n;i++) {
        int k;
        cin >> k;
        v.push_back(k);
    }
    
    
    int l=0,h=0,len=n+1,sum=v[0];
    
    while (l<=h && h<n) {
        if(sum<s) {
            sum+=v[++h];
        }
        else {
            len=min(len,h-l+1);
            sum-=v[l++];
        }
    }
    
    if(len==n+1) len=0;
    cout << len << endl;
    
}