[PS | 한 번에 맞자!] 백준 2629

0. 문제

양팔저울

2629번: 양팔저울

---

1. 문제 해석

추의 종류와 구슬의 종류가 주어졌을 때 추들로 구슬들의 무게를 판단할 수 있는가 없는가를 물어보는 문제이다. 예를 들어 예제 2를 보면 추 1,4kg으로 알 수 있는 구슬의 무게는 1,4,3,5 kg에 해당한다. 양팔 저울의 양쪽에 놓을 수 있다는 것을 주의하자!

따라서 Knapsack으로 DP를 채워나간다. DP[추의 종류][구슬 무게] = 가능?불가능? 으로 나타낼 수 있고 DP table을 채우는 것은 for문 추의 무게로 채운다. 이 때 양팔 저울의 양쪽에 모두 놓을 수 있는 것을 적용하기 위해 abs(j-추)로 저울에
j / 추 를 놓는 경우와 추 / j 를 놓는 경우를 반영해줘야 한다!

---

2. 문제 구현

N=int(input())
List=list(map(int,input().split()))
K=int(input())
target=list(map(int,input().split()))

#init
#DP[추 종류][구슬 무게]=가능 불가능
DP=[[0 for _ in range(40000+1)] for _ in range(N+1)]
DP[0][0]=1

for i in range(N):
    추 =List[i-1]
    for j in range(40000+1):
        if DP[i][j]==1: 
            DP[i+1][j+추]=1
            DP[i+1][j]=1
            DP[i+1][abs(j-추)]=1
for k in target:
    if DP[N][k]==1: print("Y",end=' ')
    else: print("N", end=' ')
print()

---

3. 한 번에 풀었는가? O