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

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

2629번: 양팔저울

 

이 문제의 핵심은 가지고 있는 추를 이용해서 확인할 수 있는 추의 무게를 모두 찾아내서 원하는 추의 무게가 있는지 없는지 확인하면 된다. 다이나믹 프로그래밍으로 분류되어있는 문제이지만 수의 제한(추의 개수는 최대 30개)이 크지 않기 때문에 완전탐색으로도 해결할 수 있다.

 

만약 추가 1이 있다고 하자. 무게 4인 추가 새로 추가된다고 하면 무게 1인 추와 무게 4인 추를 이용하여 확인할 수 있는 무게는

1. 추 자신의 무게 (1, 4)

2. 추 무게의 차이 (3)

3. 추 무게의 합 (5)

총 3가지 이다.

그러므로 추를 입력받을 때 마다 찾을 수 있는 추의 무게를 갱신해주면 된다. 중복인 무게가 들어와도 상관없지만 보기 좋게 set을 이용하여 중복인 무게를 제거하였다.

 

이후 찾고 싶은 무게의 추를 검사할 수 있으면 Y를 출력, 없으면 N을 출력하면 된다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))

candidate = []
for i in range(n):
    if len(candidate) == 0:
        candidate.append(nums[i])
    
    else:
        num = nums[i]
        
        for j in range(len(candidate)):
            diff = abs(num - candidate[j])
            add = num + candidate[j]

            candidate.append(num)
            candidate.append(diff)
            candidate.append(add)
    
    candidate = list(set(candidate))
    


t = int(input())
test = list(map(int, input().split()))

ans = []
for tc in test:
    if tc in candidate:
        ans.append('Y')
    
    else:
        ans.append('N')

print(*ans)