[백준] 19600 이진 삼진 탐색 놀이 2💫

백준 19600 이진 삼진 탐색 놀이 2

• https://www.acmicpc.net/problem/19600

틀린 풀이

• 백준 19599 이진 삼진 탐색 놀이 1 문제의 풀이를 이용하여 B[i]와 T[i]의 부분합을 계산하면 시간 초과가 발생한다

• 2중 for문의 실행 횟수: N^2
  B와 T를 계산하는 함수의 시간 복잡도: 약 O(N $*$ lgN)
  -> 총 시간 복잡도: 약 O(N^3 $*$ lgN)

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

typedef long long ll;

vector<int> A;

//Bsum[i][j]: 배열 A의 크기가 i일 때 B[0] ~ B[j]까지의 부분합
ll Bsum[5001][5001] = { 0 };
//Tsum[i][j]: 배열 A의 크기가 i일 때 T[0] ~ T[j]까지의 부분합
ll Tsum[5001][5001] = { 0 };

//A에서 이분 탐색으로 val값을 찾기 위해 필요한 비교 횟수 반환
ll binary_search(int value, int left, int right) {

	int mid = (left + right) / 2;

	if (A[mid] == value)
		return 0;

	else if (value < A[mid])
		return 1LL + binary_search(value, left, mid - 1);
	else
		return 1LL + binary_search(value, mid + 1, right);
}


//A에서 삼분 탐색으로 val값을 찾기 위해 필요한 비교 횟수 반환
ll ternary_search(int value, int left, int right) {

	int left_third = left + ((right - left) / 3);
	int right_third = right - ((right - left) / 3);

	if (A[left_third] == value)
		return 0;
	else if (A[right_third] == value)
		return 1LL;
	else if (value < A[left_third])
		return 2LL + ternary_search(value, left, left_third - 1);
	else if (value < A[right_third])
		return 2LL + ternary_search(value, left_third + 1, right_third - 1);
	else
		return 2LL + ternary_search(value, right_third + 1, right);
}

void getPrefixSum() {

	//배열 A의 크기 1 ~ 5000일 때 B와 T의 부분합 계산
	for (int n = 1; n <= 5000; ++n) {

		Bsum[n][0] = binary_search(A[0], 0, n - 1);
		Tsum[n][0] = ternary_search(A[0], 0, n - 1);

		for (int i = 1; i < n; ++i) {
			Bsum[n][i] = Bsum[n][i - 1] + binary_search(A[i], 0, n - 1);
			Tsum[n][i] = Tsum[n][i - 1] + ternary_search(A[i], 0, n - 1);
		}
	}

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for (int i = 0; i < 5000; ++i)
		A.push_back(i);
	getPrefixSum();

	int Q;
	cin >> Q;
	while (Q--) {
		int N, S, E;
		cin >> N >> S >> E;

		if (S == 0) cout << Tsum[N][E] - Bsum[N][E] << "\n";
		else cout << (Tsum[N][E] - Tsum[N][S - 1]) - (Bsum[N][E] - Bsum[N][S - 1]) << "\n";

	}
	return 0;
}

풀이

• 백준 19599 이진 삼진 탐색 놀이 1 문제의 빠른 풀이를 이용하여 B[i]와 T[i]의 부분합을 계산한다

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

//cnt[n][i]: 배열 A의 크기가 n일 때 B[i] - T[i]
int cnt[5001][5001] = { 0 };
//psum[n][i]: 배열 A의 크기가 n일 때 cnt[0] ~ cnt[i]까지의 부분합
int psum[5001][5001] = { 0 };

void binAdd(int n, int s, int e, int add) {
	if (s > e) return;

	int mid = (s + e) / 2;
	cnt[n][mid] += add++;

	binAdd(n, s, mid - 1, add);
	binAdd(n, mid + 1, e, add);
}

void terSub(int n, int s, int e, int sub) {
	if (s > e) return;

	if (s == e) {
		cnt[n][s] -= sub;
		return;
	}

	int t1 = s + (e - s) / 3;
	int t2 = e - (e - s) / 3;

	cnt[n][t1] -= sub++;
	cnt[n][t2] -= sub++;

	terSub(n, s, t1 - 1, sub);
	terSub(n, t1 + 1, t2 - 1, sub);
	terSub(n, t2 + 1, e, sub);
}

void getPrefixSum() {

	//배열 A의 크기 1 ~ 5000일 때 cnt의 부분합 계산
	for (int n = 1; n <= 5000; ++n) {

		binAdd(n, 0, n - 1, 0);
		terSub(n, 0, n - 1, 0);
		
		psum[n][0] = cnt[n][0];
		for (int i = 1; i <=  n; ++i) 
			psum[n][i] = psum[n][i - 1] + cnt[n][i];
	}

	return;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	getPrefixSum();

	int Q;
	cin >> Q;
	while (Q--) {
		int N, S, E;
		cin >> N >> S >> E;

		if (S == 0) cout << -psum[N][E] << "\n";
		else cout << -(psum[N][E] - psum[N][S-1]) << "\n";

	}
	return 0;
}