취미로 코딩하기

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

이번에 볼 문제는 백준 22662번 문제인 Pi is Three이다.
문제는 아래 링크를 확인하자.

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

글쓴이는 Stern-Brocot tree(Farey sequence)를 이용하여 문제를 해결하였다. 해당 개념을 알고 있다고 가정하고 풀이를 서술한다.

Farey sequence에서 인접한 두 항 $L=\frac{A_1}{A_2}$과 $R=\frac{B_1}{B_2}$이 사이에 원주율에서 3을 뺀 값 $P$을 포함하고 있다고 해보자. 이때, $P-L$과 $R-P$ 중 작은 값보다 더 $P$에 가까운 분수의 분모는 Farey Sequence의 성질에 의해 $A_2$ 및 $B_2$보다 큼을 관찰하자.

위 성질을 이용하면 Stern-Brocot tree를 따라 $P$에 가까운 분수를 찾아나가는 것으로 문제에서 요구하는 분수를 찾을 수 있게 된다. 이를 이용해 문제를 해결하자.

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

//stern-brocot tree
#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;
typedef long long ll;

const ld PI3 = acosl(-1) - 3;

ll A1 = 0, A2 = 1, B1 = 1, B2 = 1, C1, C2;
ld x;

void solve() {
	A1 = 0, A2 = 1, B1 = 1, B2 = 1;
	while (PI3 * A2 - A1 > x * A2 && B1 - PI3 * B2 > x * B2) {
		C1 = A1 + B1, C2 = A2 + B2;
		if (PI3 * C2 < C1) B1 = C1, B2 = C2;
		else A1 = C1, A2 = C2;
	}
	if (PI3 * A2 - A1 < x * A2) cout << A2 * 3 + A1 << '/' << A2 << '\n';
	else cout << B2 * 3 + B1 << '/' << B2 << '\n';
}

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

	cin >> x;
	while (x) {
		solve();
		cin >> x;
	}
}