BOJ 13116 : 30번 [C++]

 

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

13116번: 30번

 

문제 요약

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

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

 

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

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

 

접근

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

 

#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';
	}
}