2629. 양팔저울 (Python)

 

2629번: 양팔저울

 

풀이

 재귀를 사용하여 1)저울의 왼쪽에 추를 올리는 경우, 2)저울의 오른쪽에 추를 올리는 경우, 3)추를 저울에 올리지 않는 경우로 나누어 재귀를 통해 구할 수 있는 구슬의 무게에 대한 경우의 수를 체크한다. 

 2차원 배열 dp에는 다음과 같은 정보가 저장된다.

dp[weight][n] -> n번 추까지 사용했을 때 무게 weight를 만들 수 있는지에 대한 정보

 

 코드

from collections import defaultdict


# idx: idx번 째 추, left: 저울의 왼쪽 무게, right: 저울의 오른쪽 무게
# abs(left - right) 무게의 구슬을 추를 사용하여 측정할 수 있다.
def solve(idx, left, right):
    if idx == N:  # 모든 추에 대해서 확인했으면 측정할 수 있는 구슬 무게 기록하고 종료
        weightDict[abs(left - right)] = True
        return

    if dp[abs(left - right)][idx] == 1:  # 이미 체크한 경우 바로 종료
        return

    weightDict[abs(left - right)] = True  # 구슬 무게 기록
    dp[abs(left - right)][idx] = 1

    solve(idx + 1, left + weight[idx], right)  # 1) 왼쪽에 추를 올린다
    solve(idx + 1, left, right + weight[idx])  # 2) 오른쪽에 추를 올린다
    solve(idx + 1, left, right)  # 3) 추를 올리지 않는다


if __name__ == '__main__':
    N = int(input())
    dp = [[0 for _ in range(N+2)] for _ in range(15001)]
    weight = list(map(int, input().split()))
    M = int(input())
    case = list(map(int, input().split()))

    weightDict = defaultdict(bool)
    solve(0, 0, 0)

    for c in case:
        if weightDict[c]:
            print('Y', end=' ')
        else:
            print('N', end=' ')