[BOJ 13215 // C++] Fish

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13215번 문제인 Fish이다.
문제는 아래 링크를 확인하자.

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

13215번: Fish

이 문제는 분할정복(Divide&Conquer)으로 해결할 수 있다.

 

구간 [L,R]에 속하는 Kuching이 먹을 수 있는 생선토막 [l,r]들은 (L<R일 경우) mid = (L+R)/2에 대하여 (1) [L,mid]와 [mid+1,R] 양쪽에 걸쳐있거나 (2) [L,mid] 또는 [mid+1,R]에 완전히 포함되거나 정확히 둘중 하나를 만족시킨다. 따라서 구하는 경우의 수는 (1)의 가짓수와 (2)의 가짓수를 합하는 것으로 계산해낼 수 있다. 즉, (1)의 값을 답에 더하고, 각 (2)의 경우에 대한 부분문제를 다시 해결하는 것을 반복하는 것으로 문제를 해결할 수 있다.

 

(1)의 경우의 수는 prefix sum 배열과 정렬 및 투포인터 테크닉을 이용해 빠르게 구할 수 있다.

 

이 알고리즘의 시간복잡도는 $O(Nl{g}^{2}N)$과 같다.

 

아래는 제출한 소스코드이다.

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

ll N, K;
ll arr[200000];
ll psumL[100000], psumR[100000];
ll ans;

void func(int L, int R) {
	if (L == R) {
		if (arr[L] >= K) ans++;
		return;
	}

	int mid = (L + R) / 2;
	ll sizeL = mid - L + 1, sizeR = R - mid;
	psumL[0] = arr[mid];
	for (int i = 1; i < sizeL; i++) psumL[i] = psumL[i - 1] + arr[mid - i];
	psumR[0] = arr[mid + 1];
	for (int i = 1; i < sizeR; i++) psumR[i] = psumR[i - 1] + arr[mid + 1 + i];

	sort(psumL, psumL + sizeL);
	sort(psumR, psumR + sizeR);
	
	ll idxL = sizeL - 1, idxR = 0;
	while (idxL > -1 && idxR < sizeR) {
		if (psumL[idxL] + psumR[idxR] < K) idxR++;
		else {
			ans += sizeR - idxR;
			idxL--;
		}
	}

	func(L, mid), func(mid + 1, R);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];

	func(0, N - 1);

	cout << ans;
}