백준 1806번 부분합

백준 1806번 부분합

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include <algorithm>
#include<cmath>
using namespace std;
 
int arr[100000];
int psum[100000];
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N,S;
    cin >> N >> S;
 
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    int result = 987654321, sum = 0, lo = 0, hi = 0;
    int Count = 0;
    while (1) {
        //총합을 넘겼으면 lo증가
        if (sum >= S) {
            result = min(result, hi - lo);
            sum -= arr[lo++];
            //그러한 합을 만드는게 불가능하면 Count는 0인채로 루프 탈출
            Count++;
        }
        else if (hi == N) break;
        //총합못넘겼으면 hi증가
        else sum += arr[hi++];
    }
    if (Count == 0) {
        cout << 0;
        return 0;
    }
    cout << result;
    return 0;
}

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

문제 이름이 부분합이길래 알고리즘 해결전략 17장 부분합 파트 공부할 겸 풀어봤는데

 

모든 경우의 수를 다 테스트해 본다면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 이미 O(N^2)라 오답이네요.

구간 합 배열을 만드는게 아니라 투 포인터 라는 기법을 사용하면 쉽게 풀 수 있는 문제였습니다.