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

 

 

 

알고리즘 종류

    - Two pointers

 

 

 

사고 과정

    - 기본적인 투 포인터 알고리즘 사용

        1. 합보다 크거나 같으면 길이 갱신하고 왼쪽 포인터 옮기기

        2. 합보다 작으면 오른쪽 포인터 옮기기

 

 

 

구현(C++)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n, s;
 
int arr[100001];
 
int main(void){
    
    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    int left=0, right=0;
    int sum = arr[0];
    int answer = 987654321;
    
    while(left<=right && right<n){
        if(sum < s){
            sum += arr[++right];
        } else if(sum >= s){
            answer = min(answer, right-left+1);
            sum -= arr[left++];
        }
    }
    
    if(answer == 987654321) cout << 0 << endl;
    else cout << answer << endl;
    
 
 
}
 

 

 

 

시행착오