[백준][Python] 2629 양팔저울

아이디어

1. 추 무게의 합을 전부 구해서 dp에 체크

2. 모든 무게에 다시한번 추를 빼주며(반대쪽 저울에 올려놓으며) dp체크

 

사실 같은 추를 두번사용하는 즉 왼쪽에도 오른쪽에도 올려놓는 경우를 체크하기는 하나

양쪽에 올려봤자 안올렸을 때의 dp와 같으므로 문제없다.

(같은걸 두번 더하거나 두번뺄때가 아니면 결과 집합은 같다.)

import sys
input = sys.stdin.readline

chu_N = int(input())
chu_list = list(map(int,input().split()))

glass_ball_N = int(input())
ball_list = list(map(int,input().split()))

dp_chu = {i:False for i in range(sum(chu_list)+1)}
dp_chu[0] = True

for chu in chu_list:
    for sum_chu, exist in list(dp_chu.items()):
        if exist:
            if not dp_chu[sum_chu+chu]:
                dp_chu[sum_chu+chu] = True

for chu in chu_list:
    for sum_chu, exist in list(dp_chu.items()):
        if exist:
            if sum_chu-chu >=0 and not dp_chu[sum_chu-chu]:
                dp_chu[sum_chu-chu] = True

for ball in ball_list:
    if ball > sum(chu_list):
        print("N", end= " ")
        continue
    if dp_chu[ball]:
        print("Y", end=" ")
    else:
        print("N", end=" ")
else:
    print()