[Python 3] BOJ - 2629 "양팔저울"

 # 문제 링크

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

2629번: 양팔저울

 

 # 풀이

 개인적으로 이 문제의 핵심은 배낭 문제라고 생각한다. 문제에서 가능한 추의 무게는 500g이고 갯수는 30개이므로 가능한 추의 합의 최대값은 15000이다. 따라서 배낭문제를 위해 15000 * 30만큼의 메모리가 필요하고 이는 충분하다. 마찬가지로 450,000번의 연산은 충분히 시간안에 할 수 있다. 따라서 상태공간을 현재 i번째 추를 기준으로 무게 j가 가능한지 여부(True or False)로 정의하면 점화식은 $dp[i][j] = dp[i-1][j] \ | \ dp[i - 1][k + arr[i]], where\ k = j - arr[i]$이다. 상태 전이 도중 두 경우, 즉 현재 i번째 추를 더하지 않고도 무게 j를 만드는 경우와 i번째 추를 더해서 무게 j를 만드는 경우 둘 중 한쪽만 가능해도 무게 j를 만들 수 있기 때문에 OR 연산이 점화식에 쓰임을 알 수 있다.

 이후 가능한 모든 무게를 set에 추가한 후, 가능한 무게들에서 구슬의 무게를 뺀 무게가 set에 있다면 그 구슬의 무게는 확인이 가능하므로 Y를, 그렇지 않다면 N을 출력한다

 

 # 코드

import sys, math

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
val = sum(arr)

# dp : 현재 i번째 추에서 무게 j를 만들 수 있는지 아닌지를 나타내는 상태 공간
dp = [[False] * (val + 1) for _ in range(n)]

# 무게 0과 첫번째 추의 무게는 무조건 만들 수 있다
dp[0][0] = True
dp[0][arr[0]] = True

# 점화식
for i in range(1, n):
    for j in range(val + 1):
        if dp[i - 1][j]:
            dp[i][j] = True
            dp[i][j + arr[i]] = True
            
# check : 만들 수 있는 무게들의 집합
check = set()
for i in range(n):
    for j in range(val + 1):
        if dp[i][j]:
            check.add(j)
            
# 입력부
m = int(sys.stdin.readline())
temp = list(map(int, sys.stdin.readline().split()))
for i in temp:
    find = False
    for j in check:
        # 무게의 차가 구슬의 무게만큼이라면 가능
        if j - i in check:
            find = True
            break
    # find의 여부에 따라 정답 출력
    print('Y' if find else 'N', end=' ')