-
[Python 3] BOJ - 2629 "양팔저울"BOJ 2021. 9. 8. 12:34
# 문제 링크
https://www.acmicpc.net/problem/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=' ')
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 2250 "트리의 높이와 너비" (0) 2021.09.13 [Python 3] BOJ - 2169 "로봇 조종하기" (0) 2021.09.09 [Python 3] BOJ - 1300 "K번째 수" (0) 2021.09.07 [Python 3] BOJ - 1256 "사전" (0) 2021.09.06 [Python 3] BOJ - 14865 "곡선 자르기" (0) 2021.09.03