백준 2629. 양팔저울 (Python)

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

풀이

배낭문제(knapsack problem)를 응용한 문제이다.(12865번 문제 참고)
점화식을 아래처럼 설계한다.
dp[i][j]=i번째 추를 넣을경우, 안넣을경우, 반대편에 넣을경우 만들 수 있는 구슬의무게
즉, i-1번째 무게가 weight이고 i번째 추의 무게가 j인 경우

• dp[i][weight+j]
• dp[i][weight-j]
• dp[i][weight]

위의 3가지는 구슬의 무게로 가능한 가짓 수 이다.
이때,

• weight-j는 0보다 커야하며(무게가 음수일 수는 없다)
• 중복되는경우는 없애는 것이 좋다(재귀함수 반복 줄이기)
  dp배열이 완성된 경우 해당 구슬의 무게에 해당하는 dp배열을 순회하면서 True가 있는지 조회.

N=int(input())
li=[0]+list(map(int,input().split()))+[0]
ball_N=int(input())
ball=list(map(int,input().split()))
dp=[[0]*(15001) for i in range(N+1)]

def back(now,weight):
    if now>N or dp[now][weight]:
        return
    dp[now][weight]=1
    back(now+1,weight+li[now+1])
    back(now+1,abs(weight-li[now+1]))
    back(now+1,weight)

back(0,0)
for i in ball:
    ch=0
    if i>15000:
        print("N",end=" ")
    else:
        for j in range(1,N+1):
            if dp[j][i]==1:
                print("Y",end=" ")
                ch=1
                break
        if ch==0:
            print("N",end=" ")
        

아래의 방법은 2차원 dp배열 대신 set을 이용한 방법이다.
위와 같은 방법으로 이루어지지만, set을 이용해 훨씬 간결하게 작성된 방법.

• 추 배열을 순회하면서 우선 임시 set배열에 추의 무게(weight)를 넣어준다.
• 전체 set배열을 순회하면서, weight에 해당 set의 값(i, 이전까지의 추로 만들 수 있던 무게)를 더하거나, 뺐을때 경우를 임시 set배열에 넣어준다
• 전체 set배열에 임시 set배열을 병합해주고 반복

N=int(input())
li=list(map(int,input().split()))
ball_N=int(input())
ball=list(map(int,input().split()))
dp_set=set()

for weight in li:
    tmp_set=set()
    tmp_set.add(weight)
    for i in dp_set:
        tmp_set.add(weight+i)
        tmp_set.add(abs(weight-i))
    dp_set=dp_set.union(tmp_set)
for i in ball:
    print("Y" if i in dp_set else"N",end=" ")