문제 풀이

BOJ 13116 : 30번 [C++]

khj20006 2023. 2. 12. 06:00
반응형

 

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

 

13116번: 30번

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1

www.acmicpc.net

 

문제 요약

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

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

 

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

 

접근

문제의 조건에서 $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';
	}
}
반응형