[Day 1] BOJ 13116 : 30번

왠지 모르게 어린이 보호구역이 떠오르는 제목이다.

문제

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

2007년 수능 수리 가형 30번 문제를 푸는 문제이다.

고등학교 시절 3년을 수학에만 쏟아부었던 사람으로서, 이 문제를 보고 도저히 그냥 지나칠 수가 없었다.

문제에 써있는 것처럼, 나도 저작권 위반으로 판사님을 뵙고 싶지 않기에
궁금하다면 직접 링크를 타고 들어가보자.

• http://wdown.ebsi.co.kr/W61001/01exam/20061116/mathga1_mun.pdf

해결 전략

문제의 조건에서 $A$, $B$가 1023, 즉 $2^{10} - 1$을 넘지 않는 자연수이기 때문에
$A$, $B$가 만날 때까지 반복문을 수행하여 문제를 풀어도 시간 초과가 나지 않을 것이다.

worst case가 정답이 1이고 $A$, $B$가 맨 아래에 있는 경우이므로 시간복잡도가 $O(Tlog(max(A,B)))$이다.

결론은 그냥 naive하게 짜도 통과한다.

코드

#include <iostream>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T, A, B;
	for (cin >> T; T--;) {
		cin >> A >> B;
		while (A != B) {
			if (A > B)	swap(A, B);
			if (B % 2)	B = (B - 1) / 2;
			else	B /= 2;
		}
		cout << A * 10 << '\n';
	}
}

회고

시간 초과가 났을 땐 빠른 입출력이 보약이다.