백준 2629번 양팔저울

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

2629번: 양팔저울

입력)

첫째 줄: 추의 개수(30이하의 자연수)

둘째 줄: 추의 무게들(가벼운 순으로 500g 이하의 자연수/ 같은 무게의 추 여러개 있을 수도 있음)

셋째 줄:무게를 확인하고자 하는 구슬들의 개수

넷째 줄: 확인하고자 하는 구슬들의 무게(40,000보다 작거나 같은 자연수)

 

 

출력)

주어진 각 구슬에 대하여

확인 가능-Y

확인 불가능-N

(한 개의 줄, 각 구슬에 대한 답 사이에는 빈칸을 둬야 함)

 

 

1. 구슬의 무게가 0

2. 구슬의 무게=주어진 추 무게의 합

3. 구슬의 무게= 주어진 추 무게의 차

 

 

동적프로그래밍 개념을 사용한다.  추를 사용하여 무게를 더하거나 빼는 과정을 통해 가능한 무게를 표시하고, 이를 이용하여 주어진 구슬의 무게가 가능한지를 확인한다. 먼저 계산한 뒤에 각 구슬의 무게에 대해 가능 여부를 판단한다.

 

from sys import stdin
# 추 개수를 입력
weight_cnt = int(stdin.readline())
#추의 무게를 입력받고, 가벼운 것부터 정렬된 상태
weights = list(map(int,stdin.readline().split()))
# 구슬 개수 입력
ball_cnt = int(stdin.readline())
# 확인할 구슬 무게 입력
balls = list(map(int,stdin.readline().split()))
# 결과 저장할 리스트 초기화
result = []
# 가능한 최대 추의 무게 저장할 리스트 최고화. 최대 무게는 사용할 수 있는 추 무게의 총합
possible = [False for _ in range(sum(weights)+1)]
# 아무것도 안 올린 경우
possible[0] = True

# 더해서 가능한 경우
# check 대신 enumerate(possible[:]) 가능
for w in weights:
# 현재 가능한 무게를 복사하여 확인할 리스트를 만듦
    check = possible.copy()
# 현재 가능한 무게에 대해 반복하면서 각 무게에 대해 더한 결과가 가능하면 True로 설정
    for idx, chk in enumerate(check):
        if chk==True and possible[idx+w]==False:
            possible[idx+w] = True

# 빼서 가능한 경우
# check 대신 enumerate(possible[:]) 가능
for w in weights:
# 현재 가능한 무게를 복사하여 확인할 리스트를 만듦
    check = possible.copy()
    # 현재 가능한 무게에 대해 반복하면서 각 무게에 대해 뺀 결과가 0보다 크고 가능하면 True로 설정
    for idx, chk in enumerate(check):
        if (idx-w) >= 0:
            if chk==True and possible[idx-w]==False:
                possible[idx-w] = True

for b in balls:
# 구슬 무게가 가능한 최대 무게 초과하면 N 추가
    if b > sum(weights):
        result.append("N")
    else:
# 구슬 무게가 가능한 최대 무게 이하면 Y추가
        if possible[b]:
            result.append("Y")
        else:
            result.append("N")
        
for res in result:
    print(res, end=' ')

이 또한 구글링을 통해 공부를 했다. 어떻게 시작해야 할 지, 풀어야 할 지 감이 안 잡혔다...

이 문제에 대한 정말 많은 코드를 봤는데 이 코드가 가장 이해하기 쉽고, 내 기준 효율적이라고 생각했다.