파이썬 2629 양팔저울 - 백준

문제.

 

풀이.

양팔 저울이 잴 수 있는 무게는 양팔에 올라간 추의 무게 차이이다.

예를들어 1,3,7 무게의 추가 있다면 잴 수 있는 경우는

1, 2, 3, 4, 6, 7, 8, 10, 11의 무게를 잴 수 있다.

여기서 2, 4, 6 같은 경우에는

|왼쪽 저울 - 오른쪽 저울|의 값이다.

즉 dp[i][j] = i번쨰 추를 놓으려고 할때 현재의 무게차이 j 이다.

 

소스코드.

import sys

def scale(weight, n, now, left, right):
    new = abs(left - right)
    # possible에 현재 무게차이가 들어 있지 않다면 추가
    if new not in possible:
        possible.append(new)
    if now == n:
        return
    # 방문하는 dp가 이미 계산을 했을때는 패스
    if dp[now][new] == 0:
        scale(weight, n, now + 1, left + weight[now], right) # 왼쪽 값 증가
        scale(weight, n, now + 1, left, right + weight[now]) # 오른 쪽 값 증가
        scale(weight, n, now + 1, left, right)
        dp[now][new] = 1

input = sys.stdin.readline
n = int(input())
weights = list(map(int, input().split()))
m = int(input())
check_weights = list(map(int, input().split()))

possible = []
dp = [[0 for i in range(15001)] for j in range(n+1)]

scale(weights, n, 0, 0, 0)
for i in check_weights:
    if i in possible:
        print('Y', end=' ')
    else:
        print('N', end=' ')