Gidhub BE Developer

BOJ - 부분합

2018-02-11
goodGid

Problem

Problem URL : 부분합

Screenshots of Problem Explain

Answer Code (1) [18. 02. 11]


#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;

ll arr[100001];

int main(void) {
    ll n,m;
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        scanf("%lld",arr+i);
    }
    
    int l,r;
    l = r = 1 ;
    
    ll sum = arr[1];
    int ans = 1e9;

    while(l <= r && l<=n){
        if( sum < m ){
            if( r+1 > n)
                break;
            sum += arr[++r];
        }
        else{
            ans = ans < r-l+1 ? ans : r-l+1;
            sum -= arr[l++];
        }
    }
    
    ans = ans == 1e9 ? 0 : ans;
    cout << ans << endl;
    return 0;
}




Code Review

Answer Code (1) [18. 02. 11]

  • 슬라이딩 알고리즘이라는 걸 알고 푸니까 어렵지 않게 풀었다.

Comments

Content