2629. 양팔저울

구슬의 무게를 구하기 위해서는 두 양팔 저울무게의 차이를 구하면 된다. 쉽게 접근하면 추1번을 왼쪽에 올릴 수도, 오른쪽에 올릴 수도, 올리지 않을 수도 있다. 근데 추가 30개 까지 가능하다. 즉 3의 30승 = 205,891,132,094,649 에 해당하는 경우의 수를 가질 수 있다. 이러면 약간 불안하다. 따라서 경우의 수를 적게 만들거나 이미 계산한 것은 계산하지 않는 방식을 취해야한다.

왼쪽 오른쪽에 놓을수 있고 놓지 않을 수도 있다. -> 탐색. dfs를 생각하게 되었다.

dfs의 리턴 조건에서 추의 개수가 다 차면 리턴하면 좋을 것 같았다.

import sys;input=sys.stdin.readline
n = int(input())
weights = list(map(int,input().split()))
k = int(input())
marbles = list(map(int,input().split()))
dp = [[0 for _ in range(15001)] for _ in range(n+1)]
possible = []

def dfs(weights, n, now, left, right):
  new = abs(left - right)

  if new not in possible: 
    possible.append(new)

  if now == n : return 0

  if dp[now][new] == 0:
    dfs(weights, n, now + 1, left + weights[now], right)
    dfs(weights, n, now + 1, left, right + weights[now])
    dfs(weights, n, now+1, left, right)
    dp[now][new] = 1
dfs(weights, n, 0, 0, 0)
for i in range(0, k):
  if marbles[i] in possible:
    print("Y" , end = " ")
  else:
    print("N", end = " ")