[백준] 양팔저울

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

2629번: 양팔저울

배낭문제를 활용하여 풀이할 수 있습니다. 무게 추들을 순회하면서 현재까지 잴 수 있는 무게에서 더하거나 빼면 잴 수 있는 무게가 되게 됩니다. 예를 들어, 1, 3, 5 무게 추가 있다고 가정하면 1을 순회할 때는 {1}만 가능하고 3을 순회할 때는 {1, 3, 3 - 1 , 1 + 3}이 가능하므로 {1, 2, 3, 4}가 가능해지고 5를 순회할 때에는 {1, 2, 3, 4, 5, 1 + 5, 2 + 5, 3 + 5, 4 + 5, 5 - 1, 5 - 2, 5 - 3, 5 - 4}가 가능해지므로 {1, 2, 3, 4, 5, 6, 7, 8, 9}가 가능해집니다. 이 조합들을 set에 담아두고 무게를 잴 수 있는지 여부를 체크해주면 됩니다.

 

import sys
sys.stdin = open("input.txt", "r")
INT_MAX = sys.maxsize

input = sys.stdin.readline
n = int(input())

weights = list(map(int, input().split()))

m = int(input())

want = list(map(int, input().split()))


possible = set()

for cur in weights:
    temp = list(possible)
    # 현재까지 조합에서 더하거나 뺸 무게를 잴수가 있다.
    for p in temp:
        possible.add(p + cur)
        possible.add(abs(p - cur))
    possible.add(cur)

for w in want:
    if w in possible:
        print('Y', end=' ')
    else:
        print('N', end=' ')