백준 / 2629 양팔저울 python3

www.acmicpc.net/problem/2629

2629번: 양팔저울

설이라 본가에 내려왔지만, 노트북을 안 들고 와서 파이썬으로 문제를 풀었습니다. 

(여기 있는 컴퓨터에 C++ 컴파일러 깔기 귀찮아서 파이썬 온라인 컴파일러를 활용했습니다. 허허)

 

위 문제는 추의 무게가 주어지고 구슬의 무게가 주어졌을 때 측정이 가능한지를 묻는 문제입니다.

측정 가능한 경우는 총 3가지 입니다.

 

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 = []
# 가능한 최대 추의 무게는 sum(weights)
possible = [False for _ in range(sum(weights)+1)]
# 아무것도 안 올린 경우
possible[0] = True

# 더해서 가능한 경우
# check 대신 enumerate(possible[:]) 가능
for w in weights:
    check = possible.copy()
    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()
    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:
    if b > sum(weights):
        result.append("N")
    else:
        if possible[b]:
            result.append("Y")
        else:
            result.append("N")
        
for res in result:
    print(res, end=' ')