[알고리즘] 백준 13116 (파이썬 풀이)

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

13116번: 30번

문제

혹시 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를 넣었을 때 답을 구하라는 의미이다

출력

각 테스트 케이스에 대해 답을 한 줄에 하나씩 출력한다.

 

해결코드

t = int(input())
for i in range(t):
    a,b = map(int, input().split())
    while(True):
        if(a>b):
            a //= 2
        elif(a<b):
            b //= 2
        elif(a==b):
            print(a*10)
            break

문제풀이

일단 링크에서 문제 그림을 보면 결국에 공통된 부모 노드를 찾으라는 문제이다.

문제에서 부모노드는 자식노드 값의 절반이다.

그래서 계속해서 2로 나누다 보면 결국에 부모노드로 도달한다는 원리이다.

코드를 보자

t에 테스트케이스 수를 입력받는다.

테스트케이스 수만큼 for문을 돌린다.

공백을 포함하여 a,b를 입력받는다.

부모노드를 찾을때까지 while문을 돌린다.

만약 a가 b보다 크다면 a를 2로 나눈 몫을 다시 a에 넣는다.

반대로 b가 더 크다면 b를 2로 나눈 몫을 다시 b에 넣는다.

반복하다보면 a와 b가 같아지는 시점이 있는데 그때가 a와b의 부모노드이다.

둘이 같아지면 문제에서 부모노드*10을 하라고 했으니까 그냥 a에 10배를 하면 된다.

그리고 무한반복문을 종료한다.