[Python] 백준 2629 - 양팔저울

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

 

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

 

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

---

 

풀이

냅색 문제의 응용이다. (근데 굳이 평범한 배낭 문제처럼 안풀어도 되고 1차원 DP로도 풀 수 있다)

확인하고자 하는 물체의 무게가 최대 40000이므로 그냥 길이가 40001인 불리언 DP리스트를 만들자.

 

일단 0은 True이다.

 

각각의 추에 대해, True로 바뀌게 되는 물건들은 (전에 가능했던 값 + 추 무게) 그리고 |(전에 가능했던 값 - 추 무게)| 이다.

그냥 이거를 이중 for문을 돌면서 시행해주면 되는데, 다만 방금 업데이트 했던 물건을 바로 또 업데이트하지 않도록 무게를 더할때는 반복문을 거꾸로 돌리고, 무게를 빼줄때는 반복문을 원래대로 돌리면 될 것이다.

 

N = int(input())
arr = list(map(int, input().split()))
M = int(input())
test = list(map(int, input().split()))
dp = [False]*40001
dp[0] = True
idx = sum(arr)
for i in range(N):
    for j in range(idx, -1, -1):
        if dp[j]:
            dp[j+arr[i]] = True
    for j in range(idx + 1):
        if dp[j]:
            dp[abs(j-arr[i])] = True
for i in range(M):
    if dp[test[i]]:
        print('Y', end = ' ')
    else:
        print('N', end = ' ')