[BOJ][C++] 백준 14246번 : K보다 큰 구간

https://www.acmicpc.net/problem/14246

 

문제

 n$n$개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j]$[i,j]$ (i≤j)$i≤j)$의 합이 k$k$보다 큰 모든 쌍 (i,j)$(i, j)$의 개수를 출력하시오.

입력

첫째 줄에는 자연수의 개수 n$n$이 주어진다. (1≤n≤100000$1≤n≤100\,000$)

다음 줄에는 자연수 n$n$개가 주어진다. 자연수는 100000$100\,000$보다 크지 않다.

그 다음 줄에는 자연수 k$k$가 주어진다. (1≤k≤1000000000$1≤k≤1\,000\,000\,000$)

출력

특정 구간 [i,j]$[i,j]$의 합이 k$k$보다 큰 모든 쌍 (i,j)$(i,j)$의 개수를 출력하시오.

 

풀이

길이가 고정되지 않은 슬라이딩 윈도우 문제

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    cin >> k;
    
    long long ans = 0;
    int left=0, right=0;
    long long sum = v[0];
    while(right<n) {
        if(sum > k) {
            ans += n-right;
            sum -= v[left];
            left++;
        } else {
            right++;
            sum += v[right];
        }
    }
    
    cout << ans;
    
    return 0;
}