백준 14246번 k보다 큰 구간 (C++)

알고리즘 개념: 투포인터

투포인터에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다. 

알고리즘 공부 2주차: 투포인터 개념

알공 2주차: 투포인터 개념

백준 2003번 수들의 합 2

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

14246번: K보다 큰 구간

백준 문제 설명

 

예제 보려면 더보기 클릭

예제 입력 1

5
1 2 3 2 1
7

예제 출력 1

3

예제 입력 2

5
1 1 1 1 1
2

예제 출력 2

6

---

문제 설명

특정 구간(i부터 j까지) 더했을 때 k보다 큰 구간의 모든 경우의 수를 구하는 문제이다.

예제 1) n=5 , k=7이고 1,2,3,2,1 이란 수가 주어졌을 때를 예시로 보자. 

투포인터 예제 설명1

처음 front와 back은 모두 0을 가리킨다. 

sum < k 이므로 back을 1 더해준다. 

투포인터 예제 설명2

똑같이 sum < k이므로 back을 1씩 더해준다. 

투포인터 예제 설명3

투포인터 예제 설명4

sum > k이므로 개수를 센다.

이때 back을 움직여가며 일일이 개수를 세면 안 된다.

투포인터 예제 설명5

현재 back의 값은 3이고 전체 크기의 값은 5이다.

또한 현재 구간에서 sum보다 큰 경우의 수는 back이 3일 때와 4일 때 총 2개이다.  

즉 남은 개수는 count = n - b을 통해 구할 수 있다. 

그리고 sum > k이므로 front값을 늘려준다. 

front를 1씩 더할 때는 더하기 전 미리 sum에서 이전 front 인덱스 값을 빼주는 것이 중요하다.

투포인터 예제 설명6

k보다 큰 개수를 구하는 것이므로 k와 같을 땐 그냥 b를  +1 해준다. 

 

투포인터 예제 설명7

현재 b=4, n=5이므로 count += n-b에서 count값은 3이 된다. 

투포인터 예제 설명8

이 이후로도 같은 과정이 반복되므로 생략.

정리하자면 앞서 말했던 count값이 일일이 계산하여 1씩 더하는 것이 아닌 count  = n-b 라는 식을 이용하는 것이 결정적 힌트인 것 같다. 

 

---

제출한 코드(C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long int;
vector <long long int> v;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,a,sum=0,cnt=0,k;
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++){
		cin >> v[i];
	}
	cin >> k;

	ll f = 0, b = 0;
	sum = v[f];
	while (1) {
		//if (sum == k) cnt++;
		if (sum <= k) {
			b++;
			if (b == n) break;
			sum += v[b];
		}
		else {
			if (b < n) cnt += n - b;
			sum -= v[f];
			f++;
		}
		
	}
	cout << cnt;

}