파이썬으로 양팔 저울과 거듭제곱 무게추를 활용해 물체 측정 가능 여부 확인하기

문제 소개

a⁰, a¹, a², …, a¹⁰⁰처럼 거듭제곱 형태의 무게추가 주어져 있다고 가정해 보겠습니다. 여기서 'a'는 정수입니다. 그리고 저울의 양쪽 접시 모두에 무게추를 올릴 수 있는 양팔 저울이 하나 있습니다. 우리가 풀어야 할 문제는, 무게가 W인 어떤 물건을 이 무게추들로 측정할 수 있는지 판별하는 것입니다.

예를 들어 입력이 a = 4, W = 17이라면 결과는 True입니다. 사용 가능한 무게추는 a⁰ = 1, a¹ = 4, a² = 16이며, 16 + 1 = 17을 만들어 낼 수 있기 때문입니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 각 무게추마다 세 가지 선택지가 존재한다는 것입니다.

물건이 있는 반대편 접시에 놓는다 (+)
물건과 같은 편 접시에 놓는다 (−)
아예 사용하지 않는다 (0)

따라서 모든 무게추에 대해 이 세 가지 경우를 재귀적으로 탐색하면 됩니다. 탐색 도중 남은 무게 차이(itemWt)가 0이 되는 순간이 오면, 목표 무게를 정확히 측정할 수 있는 것입니다.

구체적인 알고리즘은 다음과 같습니다.

found 플래그를 False로 초기화합니다.
재귀 함수 util(idx, itemWt, weights, N)을 정의합니다.
found가 이미 True라면 즉시 반환하여 불필요한 탐색을 줄입니다.
itemWt가 0이면 found를 True로 설정하고 반환합니다.
idx가 N보다 크면 더 이상 사용할 무게추가 없으므로 반환합니다.
현재 무게추를 사용하지 않는 경우: util(idx + 1, itemWt, weights, N)
현재 무게추를 더하는 경우: util(idx + 1, itemWt + weights[idx], weights, N)
현재 무게추를 빼는 경우: util(idx + 1, itemWt - weights[idx], weights, N)

메인 함수에서는 다음 과정을 수행합니다.

a가 2 또는 3이면 항상 True를 반환합니다. 모든 정수는 2의 거듭제곱(이진법) 또는 3의 거듭제곱(균형 삼진법)의 조합으로 표현할 수 있기 때문입니다.
크기 100의 리스트를 0으로 초기화하고, weights[0] = 1(a⁰)부터 시작해 a의 거듭제곱을 순서대로 저장합니다.
무게추 값이 10⁷을 초과하면 생성을 중단합니다. 목표 무게보다 지나치게 큰 무게추는 필요 없기 때문입니다.
util(0, W, weights, total_weights)를 호출해 탐색을 시작합니다.
found가 True면 True를, 그렇지 않으면 False를 반환합니다.

예제 구현

아래 코드를 통해 더 잘 이해해 보겠습니다.

found = False

def util(idx, itemWt, weights, N):
    global found
    if found:                                          # 이미 답을 찾았으면 탐색 종료
        return
    if itemWt == 0:                                    # 목표 무게를 정확히 맞춘 경우
        found = True
        return
    if idx > N:                                        # 더 이상 사용할 무게추가 없음
        return
    util(idx + 1, itemWt, weights, N)                  # 현재 무게추 미사용
    util(idx + 1, itemWt + weights[idx], weights, N)   # 반대편 접시에 놓기 (+)
    util(idx + 1, itemWt - weights[idx], weights, N)   # 같은 편 접시에 놓기 (-)

def solve(a, W):
    global found
    if a == 2 or a == 3:                               # 2, 3의 거듭제곱이면 모든 정수 표현 가능
        return True
    weights = [0] * 100
    total_weights = 0
    weights[0] = 1                                     # a^0 = 1
    i = 1
    while True:
        weights[i] = weights[i - 1] * a                # a의 거듭제곱 무게추 생성
        total_weights += 1
        if weights[i] > 10**7:                         # 지나치게 큰 무게추는 제외
            break
        i += 1
    util(0, W, weights, total_weights)
    if found:
        return True
    return False

a = 4
W = 17
print(solve(a, W))

입력

4, 17

출력

True

동작 원리 살펴보기

a = 4일 때 생성되는 무게추는 1, 4, 16, 64, … 입니다. 목표 무게가 17이라면, 물건이 있는 접시 반대편에 16과 1을 함께 올리면 저울이 균형을 이룹니다. 재귀 함수는 이 조합을 자동으로 찾아내 True를 반환하게 됩니다.

한 가지 참고할 점은 시간 복잡도입니다. 무게추 하나당 세 가지 선택지가 있으므로 최악의 경우 O(3ⁿ)의 탐색이 필요하지만, 답을 찾는 즉시 탐색을 중단하는 가지치기(pruning) 덕분에 실제로는 훨씬 빠르게 동작하는 경우가 많습니다.