문제 링크: https://www.acmicpc.net/problem/10725

Thumbnail: Photo by Jingming Pan (Unsplash)

이진수로 생각해보면 금방 풀 수 있었는데, 직관적으로 풀이가 떠오르지 않았어서 정리해봅니다.

풀이

문제의 번역에 살짝 오역이 있어, 마법을 사용한 횟수를 출력한다고 생각하면 됩니다.

기본적으로는, $A$ 또는 $B$ 둘 중에 아무거나 기준으로 잡고 금을 쪼개가며 해당 수를 0으로 만들때까지 빼주면 됩니다.

전체 코드

input = open(0).readline
for _ in range(int(input())):
    N, A, B = map(int, input().split())
    if A % 2 == 1: # 홀수 단위로 자르려면 무조건 1까지 나눠야 한다.
        print(N)
    else:
        magic_cnt = -1
        total_gold = 1 << N # 2^N
        while A > 0:
            if A >= total_gold:
                A -= total_gold
            total_gold >>= 1
            magic_cnt += 1
        print(magic_cnt)

이진수로 풀어보자

간단히 생각해보면, 마법의 발동마다 금의 무게를 절반으로 나누는 것은 해당 수를 이진수로 변환하는 것으로 생각할 수 있습니다.

두 수 $A$, $B$를 이진수로 변환한 뒤, 각각의 이진수 표기에서 가장 오른쪽(가장 낮은 자리)에 1이 나타나는 수를 찾아 필요한 마법의 횟수를 계산할 수 있다.

input = open(0).readline
for _ in range(int(input())):
    N, A, B = map(int, input().split())
    if A % 2 == 1: # 홀수 단위로 자르려면 무조건 1까지 나눠야 한다.
        print(N)
    else:
        a_n = 1
        b_n = 1
        a_cnt = 0
        b_cnt = 0
        # A의 이진수 표기에서 가장 낮은 1의 자리를 찾는다.
        while a_n & A == 0:
            a_cnt += 1
            a_n <<= 1
        # B의 이진수 표기에서 가장 낮은 1의 자리를 찾는다.
        while b_n & B == 0:
            b_cnt += 1
            b_n <<= 1
        # 둘 중 더 낮은 자리를 기준으로 마법을 사용한다.
        print(N - min(a_cnt, b_cnt))