[백준] 19599 이진 삼진 탐색 놀이 1💫

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

풀이

• A에서 삼분 탐색으로 val값을 찾기 위해 필요한 비교 횟수를 구하는 함수 구현에 주의

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

typedef long long ll;

int N;
vector<int> A;

//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);
}

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

	cin >> N;

	for (int i = 0; i < N; ++i)
		A.push_back(i);

	int res1, res2, res3;
	res1 = res2 = res3 = 0; 
	for (int i = 0; i < N; ++i) {
		ll B, T;
		B = binary_search(A[i], 0, N - 1);
		T = ternary_search(A[i], 0, N - 1);

		if (B < T) ++res1;
		else if (B == T) ++res2;
		else if (B > T) ++res3;
	}
	
	cout << res1 << "\n" << res2 << "\n" << res3;
	return 0;
}

⚡빠른 풀이

• https://www.acmicpc.net/source/22065593

• 나의 풀이: 메모리 5220KB, 시간 60ms
  빠른 풀이: 메모리 3972KB, 시간 4ms

• 더 빠른 풀이를 발견하였지만, 아직 이해하지 못했다

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

int cnt[500001] = { 0 };

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

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

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

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

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

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

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

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

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

	int N;
	cin >> N;

	binAdd(0, N - 1, 0);
	terSub(0, N - 1, 0);

	int res1, res2, res3;
	res1 = res2 = res3 = 0;
	for (int i = 0; i < N; i++) {
		if (cnt[i] < 0) ++res1;
		else if (cnt[i] == 0) ++res2;
		else if (cnt[i] > 0) ++res3;
	}

	cout << res1 << "\n" << res2 << "\n" << res3;
	return 0;
}