[백준/python]2629번 양팔저울 - knapsack

백준 2629번 양팔저울 파이썬

출처 - https://www.acmicpc.net/problem/2629

냅색을 1차원 배열로 풀 때 같은 종류의 보석을 2번 이상 사용하지 않도록 주의해야 한다.

해당 문제도 냅색으로 접근하게 되면 dp를 갱신하며 같은 추를 2번 이상 사용하지 않도록 알고리즘을 설계해야 한다. 이를 위해 해당 추를 사용하여 무게를 갱신한 경우 dp에 dp의 인덱스 크기와 동일한 무게를 확인할 수 있는 지 저장함과 동시에 추의 인덱스를 저장하여 갱신하지 않도록 했다.

1. 풀이

2. 코드

#양팔 저울
N=int(input())
weight = list(map(int, input().split()))
T= int(input())
question = list(map(int, input().split()))
dp= [ [-1,-1] for _ in range(40001)]

for i in range(N):
    now = weight[i]
    
    for j in range(1,15000): 
        
        if dp[j][0]==1 and dp[j][1]!=i:
            
            new_add=now+j
            new_sub=abs(j-now)
            
            if dp[new_add][0] !=1:
                dp[new_add][0] =1
                dp[new_add][1] =i
            
            if dp[new_sub][0]!=1:
                dp[new_sub][0]=1
                dp[new_sub][1]=i
                
    if dp[now][0] !=1:    
        dp[now][0] = 1
        dp[now][1] = i

sol=[]
for q in (question):
    if dp[q][0]==1:
        sol.append('Y')
    else:
        sol.append('N')
print(*sol)