BOJ 26868 Focusing on Costs

문제 링크입니다.

관찰

두 변의 길이가 각각 $\sqrt{a}, \sqrt{b}$인 직각삼각형의 빗변의 길이는 $\sqrt {a+b}$ 입니다.

이 점을 생각하면서 주어진 연산을 가지고 만들 수 있는 연산을 생각해 봅시다.

• $\cos (0) = 1$
• $\sin (\arctan (\sqrt{a \over b}) ) = \sqrt{a \over a+b}$
• $\tan (\arccos (\sqrt{a \over b}) ) = \sqrt{b-a \over a}$
  • $\tan (\arccos (\sin (\arctan (\sqrt{a \over b}) ) ) ) = \sqrt{b \over a}$

이제 우리는 이 연산들만 가지고 모든 답을 찾을 수 있습니다.

갑자기 정수론

루트 안의 $a \over a+b$를 $a \over b$로 바꾼다는 건 궁극적으로 $b$를 $a$로 나눈 나머지를 구하는 것과 같습니다.

$a \le b$가 유지되도록 둘을 적당히 swap하면서 이를 반복하는 알고리즘이 유클리드 호제법이라는 이름으로 잘 알려져 있습니다. 위에서 swap과 큰 값 - 작은 값의 반대 방향으로의 연산을 만들어 두었습니다.

고로, 비율이 0이나 1이 될 때까지 호제법을 역방향으로 따라가면서 연산을 구성해 주면 필요한 답을 얻을 수 있습니다. 최종 답이 루트가 없는 $a \over b$가 나와야 하므로, 문제를 풀 때는 루트를 벗긴 상태로 삼각함수들을 다루기 위해 $a^2 \over b^2$을 구하는 것으로 구현하는 것이 좋습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

stack<string> stk;

void gcd(int a, int b){
	if(!a) return;
	if(a == b){
		stk.push("cos");
		return;
	}
	if(a > b){
		stk.push("tan");
		stk.push("acos");
		stk.push("sin");
		stk.push("atan");
		gcd(b, a); return;
	}
	stk.push("sin");
	stk.push("atan");
	gcd(a, b-a); return;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int a, b; cin >> a >> b; a *= a; b *= b;
	gcd(a, b); cout << stk.size() << '\n';
	while(stk.size()){
		cout << stk.top() << ' ';
		stk.pop();
	}
}