문제
혹시 2007학년도 대학수학능력시험 수리영역 가형 이산수학 30번 문제를 아는가? 여러분은 수능을 치는 수험생의 마음으로 이 문제를 해결해야만 한다.
하지만 우리는 저작권 위반으로 판사님을 뵙고 싶지 않았기 때문에 이 문제를 직접 수록할 수는 없었다. 아래 링크 중 하나를 클릭해서 pdf 파일을 내려받아 가장 마지막 페이지를 보면, 위의 그림과 아주 유사한 문제가 하나 있을 것이다. 여러분은 바로 그 문제를 해결해야만 한다.
http://wdown.ebsi.co.kr/W61001/01exam/20061116/mathga1_mun.pdf
http://www.suneung.re.kr/boardCnts/fileDown.do?fileSeq=e7700624691c4dcb8a2cfc3f959204fe
문제를 그대로 내면 재미없기 때문에, 우리는 위 그림과 같이 33과 79가 적혀 있던 부분을 하얀색 직사각형으로 가렸다. 그림에서 흐릿하게 보이는 모든 부분은 원래 문제와 다르지 않다.
빈 칸에 들어갈 두 자연수가 주어졌을 때 문제를 해결하는 프로그램을 작성하자.
입력
첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 023, A ≠ B)가 공백을 사이로 두고 주어진다. 이는 첫 번째 빈 칸에는 A를, 두 번째 빈 칸에는 B를 넣었을 때 답을 구하라는 의미이다
출력
각 테스트 케이스에 대해 답을 한 줄에 하나씩 출력한다.
해설
트리 구조를 다루는 문제지만, 수능 수리 영역에 등장한 문제인 탓인지 수학으로도 해결이 가능하다. 기본적인 접근법은 각 노드의 부모 노드를 순회하면서 같은 순간에 순회 멈추고, 해당 값을 출력하는 것이다.
그렇다면 여기서 따져야 할 점들이 있다. 해당 노드의 높이를 따져야 하며, 어떻게 부모 노드를 순회 할 것이냐 하는 점이다. 높이는 이진 트리라는 점 때문에 을 이용하여 해결이 가능하다. 그리고 1 부터 시작하여 순차적으로 2, 3 이런 식으로 저장 되고 있음에 주목하자. 그렇기 때문에 부모 노드의 값은 현재 노드의 값을 2로 나누면 부모 노드의 값을 구할 수가 있다.
그리고 입출력에 관한 설정을 해줘야 함을 주의해라. 딱히 시간 초과 할 로직이 아닌것 같아서 그냥 제출했는데, 시간 초과가 떠버렸다. 그래서 첫 3줄의 설정을 하고 나니 비로소 정답 판정을 받았다.
#include <iostream>
#include <cmath>
auto main(int argc, char* argv[]) -> int {
std::ios_base :: sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
auto t = 0;
std::cin>>t;
while(t--) {
auto a = 0;
auto b = 0;
std::cin>>a>>b;
while(a != b) {
auto ah = std::ceil(std::log2(a));
auto bh = std::ceil(std::log2(b));
if(ah > bh) a = a/2;
else if(bh > ah) b = b/2;
else if(bh == ah) {
a = a/2;
b = b/2;
}
}
std::cout<<b * 10<<std::endl;
}
return 0;
}