[BaekJoon] 1806번 부분합

• 이 문제는 C/C++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 부분합을 구하는 방법을 3중 for문을 이용해서 하나씩 덧셈을 하여 s를 넘었는지 확인하는 방법이 기본적으로 떠올릴 수 있습니다.
• 그리고 부분합 구하는 방법을 조금 배우신 분이라면 새로운 배열을 만들어 처음부터 해당 인덱스까지의 원소들의 합을 나타내는 배열을 만듭니다. 이후 2중 for문을 이용하여 sum(j) - sum(i)가 s가 넘었는지 확인하면 시간복잡도를 낮출 수 있습니다.
• 하지만 N의 크기는 10만이라 O(n2)이여도 시간초과가 발생하기 때문에 투 포인터 라는 알고리즘을 사용해서 풀어야 합니다.
• 투 포인터 를 사용하면 O(N)으로 해결할 수 있습니다.

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

int main(){
    int arr[100000];
    int n,len;
    cin>>n>>len;

    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    int result = 1000000;
    int value = arr[0];
    int s = 0;
    int e = 0;
    while(s!=n && e!=n){
        if(value>=len){
            result = min(result, e-s+1);
            value-=arr[s++];
        }else{
            value+=arr[++e];
        }
    }
    if(result == 1000000){
        result = 0;
    }
    cout<<result;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.