[Algorithm] 1806: subtotal

📦1806: subtotal

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-19
문제 확인하기

풀이

• 이중 for 문을 사용할 경우 sum을 처음부터 새로 더해가면서 구해야 하기 때문에 시간초과가 발생한다.
• 때문에 sum, 누적합을 갱신해줘야 한다.
• start, end가 0부터 시작해서 start는 end까지, end는 N까지로 범위를 지정한다.
• 이 안에서 목표값까지 도달하지 않는다면 end를 늘려 목표값을 넘길 수 있도록 만들고 목표값에 도달하면 start를 늘려 최소 범위를 찾을 수 있도록 한다.

#include <iostream>
 
#define endl '\n'
using namespace std;
 
int N, S;
int arr[100001];
int res, sum=0;
 
void Input(){
    cin >> N >> S;
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
}
 
void Solution(){
    res = INT32_MAX;
    sum = arr[0];
    int start = 0;
    int end = 0;
    while(start <= end && end < N){
        if(sum >= S) res = min(res, end-start+1);
        if(sum < S){
            end++;
            sum += arr[end];
        }
        else{
            sum -= arr[start];
            start++;
        }
    }
    if(res == INT32_MAX) cout << 0 << endl;
    else cout << res << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}