[C++] 백준 1806 : 부분합

문제

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

 

 

 

풀이

 입력과 동시에 누적합을 구한다.

n_sum[i] = n_sum[i-1]+n;

 

 

투포인터를 이용하여 구간합이 S 이상인 구간을 구한다.

- 구간합이 M 이상인 경우, start++
- 구간합이 M 이상이면서, 해당 구간의 길이가 최솟값인 경우 구간 길이 최솟값 갱신

- 구간합이 M 미만인 경우, end++

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, s, ans = 200001;
int arr[100001];
int n_sum[100001];
int main() {
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
        n_sum[i] = n_sum[i-1]+arr[i]; // 구간합 계산
    }
    
    // 투포인터
    int start = 0, end = 1;
    while(end<=n){
        int sum = n_sum[end] - n_sum[start];
        if(sum >= s){ 
            start++; // 구간합이 S 이상이면 start 증가
            if(end-start+1 < ans){
                ans = end-start+1; // 구간 길이 최솟값 갱신
            }
        }
        else{
            end++; // 구간합이 S 미만이면 end 증가
        }
    }
    
    if(ans == 200001){
        cout << 0 << "\n"; // S 이상의 구간합을 찾을 수 없는 경우 0 출력
        return 0;
    }
    
    cout << ans << "\n";
    return 0;
}