[백준 1806] 부분합

문제풀이

 

이중포문으로 돌리면 시간 초과가 날것이다. 두개의 포인터를 통해 부분합보다 크면 왼쪽을 줄이고 작으면 오른쪽을 한칸이동하는 방식으로 탐색하여 가장 짧은 길이를 반환한다.

 

소스코드

 

#include <iostream>
#include <algorithm>
#define MAX 1000001
using namespace std;
 
int arr_size,S;
int arr[MAX];
 
int main() {
    cin>>arr_size>>S;
    for(int i=0;i<arr_size;i++){
        cin>>arr[i];
    }
    
    int min_length = MAX;
    int left=0;
    int right=0;
    int sum = arr[0];
    while(left<=right && right<arr_size){
        if(sum<S){ //합이 S보다 작을때
            right +=1;
            sum += arr[right];
        }
        else{//넘을때
            //cout<<left<<","<<right<<":"<<sum<<endl;
            min_length = min(min_length, right-left+1);
            sum -=arr[left];
            left++;
        }
    }
    if(min_length==MAX)
        min_length=0;
    
    cout<<min_length<<endl;
    return 0;
}

 

문제 링크 : https://www.acmicpc.net/problem/1806