양팔저울

내가 푼 코드...

n = int(input())
pen_lst = list(map(int,input().split()))
k = int(input())
target_lst = list(map(int,input().split()))
graph = [[False]*40001 for _ in range(n+1)]

# 더하기 
for idx in range(1,n+1):
  pen = pen_lst[idx-1]
  graph[idx][pen] = True
  # print(f'pen : {pen}')
  for i in range(1,40001):
    if graph[idx-1][i] == True:
      graph[idx][i] = True
      if i + pen < 40001:
        graph[idx][i+pen] = True

# 빼기
for pen in pen_lst:
  for i in range(1,40001):
    if graph[-1][i] == True:
      if i - pen > 0:
        graph[-1][i-pen] = True

# 출력
for target in target_lst:
  if graph[-1][target] == True:
    print('Y', end=' ')
  else:
    print('N', end=' ')

배낭 문제 여러개 풀어 보던 중에 하루종일 걸려 풀었다...
일단 작은 추 부터 2차원 배열에 순서대로 넣어준다.
행은 추의 종류, 열은 무게로 해서 만들 수 있는 배열은 true로 만들어 주었다.
1차원 배열로 하면 이전에 최신화 한 값을 참조하게 되어 원하는 대로 구현이 안되었다.

빼기로 가능한 경우의 수는 모든 더하는 경우를 먼저 구한 후에 추 무게 순서 상관없이 빼서 만들 수 있는 모든 수를 구해주면 되었다.