백준-양팔저울(feat.Python)

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

import sys
from collections import defaultdict
input = lambda : sys.stdin.readline().rstrip()
def dfs(idx,r,l) :
    w = abs(r-l)
    if not df[w]:
        df[w] = 1
    if idx == n : return
    if d[idx][w] == 0:
        # 오른쪽 저울
        dfs(idx+1, r + weights[idx], l)
        # 저울에 올리지 않음
        dfs(idx + 1, r, l)
        # 왼쪽 저울
        dfs(idx + 1, r, l+ weights[idx])
        d[idx][w] = 1

n = int(input())
weights = list(map(int,input().split()))
marble = int(input())
marbles = list(map(int,input().split()))
df = defaultdict(int)
d = [[0]*15001 for i in range(n+1)]

dfs(0,0,0)
ans =[]
for m in marbles:
    ans.append('Y') if df[m] else ans.append('N')

print(' '.join(ans))

저울에 추를 왼쪽으로 올리는 경우, 안 올리는 경우, 오른쪽으로 올리는 경우로 나누고, dfs를 돌린다. 중복되는 경우를 방지하기 위해 2차원 테이블 d[idx][w]를 사용했다.

d[idx][w] : idx번째 추를 올렸을 때, 무게가 w인 경우 이미 만들었으면 1, 만든 적 없으면 0