[백준 파이썬] 2629 양팔저울

📌문제 출처

백준 단계별 문제풀이 - 동적계획법 2단계
https://www.acmicpc.net/problem/2629

2629번: 양팔저울

❓ 문제

 

❗ 풀이

• deque와 defaultdict 사용

📗 풀이 코드

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
_ = int(input())
weights = deque(list(map(int,input().split())))
_ = int(input())
marbles = deque(list(map(int,input().split())))
dp = defaultdict(int) # dp에 새로운 값을 넣기 쉽고, 연산이 빠르게 하도록 defaultdict 사용
dp[0] = 0 # while문 첫번째 반복 시에 key_list를 뽑기 위해 미리 넣어준다.
while weights:
    w = weights.popleft()
    key_list = list(dp.keys()) # dp.keys()는 중간에 변경되기에 list형태로 만들어서 복사해서 for문 진행
    for key in key_list : # key 하나씩 돌면서
        dp[key+w] = dp[abs(key-w)] = 1 # dp값 변경
ans = ''
while marbles :
    marble = marbles.popleft()
    ans += 'Y ' if dp[marble] else 'N ' # 1이면 Y, 0이면 N
print(ans[:-1]) # 끝에 공백있으므로

📗 코드 해설

• 추와 구슬을 모두 deque에 담아서 확인을 빠르게 할 수 있도록 만든다.
• dp에는 모든 무게를 담기에는 시간이 부족할 수 있으니(최대 40000), 확인 가능한 무게만 담도록 dict로 설정
• 새로운 확인 가능한 무게를 쉽게 추가할 수 있도록 defaultdict(int)로 설정
  defaultdict에 존재하지 않는 key 값을 주면 int의 경우 value로 0을 반환한다.
• 추를 하나씩 꺼내고, 기존에 있던 확인 가능한 무게(dp의 key)를 반복문으로 하나씩 꺼낸다.
• 이때 추가되는 확인가능한 무게는 원래 무게 - 추 무게, 원래 무게 +추 무게 이므로 dp에 새로운 key 값으로 새로운 무게를 넣어준다.(차이는 음수일 수 있으므로 절대값 반영)
• 구슬을 하나씩 반복하며 dp의 key값으로 넣어 조건에 따라 Y와 N을 ans에 추가한다.