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

1) 문제설명

백준 Online Judge 14246번 K보다 큰 구간

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

14246번: K보다 큰 구간

 

2) 아이디어

presum(누적합)을 이용하여 presum배열에 누적된 합을 저장하고 그것을 이용해서 구간의 합을 구한다.

구간의 합이 K보다 큰 경우에만 while문을 진입하여 k보다 큰 쌍의 개수를 +1 한다.

★ 실행이 O(n^2)이 되지 않게 구현해야한다.

 

3) 코드

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

long long presum[100001];
long long arr[100001];

int main() {
	long long n,k;
	cin >> n;
	// 누적합(presum을 구하는 코드)
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		presum[i] = presum[i - 1] + arr[i];

	}
	
	cin >> k;
	long long cnt = 0;
	// 특정구간의 합이 K보다 큰 쌍의 갯수를 찾는 LOOP
	for (int i = 1; i <= n; i++) {
		int j = 0;
		while (presum[i] - presum[j] > k) { // 구간의 합이 K보다 큰 경우에만 loop 진입
			cnt++; // k보다 큰 모든 쌍의 갯수를 센다.
			j++;
			if (j == i) { // j와 i가 같으면 구간의 합은 0이므로 그때 loop 탈출
				break;
			}
		}
		
	}
	cout << cnt << endl;

}