[백준/1943] 동전 분배 (Python)

Problem : https://www.acmicpc.net/problem/1943

1943번: 동전 분배

 

Difficulty : Gold 3

 

Status : Solved (pypy3)

 

Time : 00:17:34

 

---

 

문제 설명

 

 

윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.

그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.

하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.

이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.

 

 

입력 및 출력

 

입력

 

세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이고, 같은 금액을 가진 동전이 두 번 이상 주어지는 경우는 없다.

 

출력

 

첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

 

입력 예시

 

2
500 1
50 1
3
100 2
50 1
10 5
3
1 1
2 1
3 1

 

출력 예시

 

0
1
1

 

 

---

 

풀이

 

DP로 풀 수 있는 대표적인 배낭 문제. 이에 대한 설명은 생략하도록 한다.

주의점은, 애초에 문제를 풀 수 없는 경우(가치의 총합이 2로 나누어 떨어지지 않을 때)만 잘 체크하면 된다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline

def solve() :
  N = int(input())
  coin_list = [ list(map(int, input().split())) for _ in range(N) ]    
  target_value = sum([c[0]*c[1] for c in coin_list])
  if target_value % 2 :
    return 0
  target_value //= 2

  q = deque([0])
  for i in range(N) :
    coin, cnt = coin_list[i]
    next_q = deque()
    visited = [False]*(target_value+1)
    while q :
      cur = q.popleft()
      for j in range(cur, cur+coin*cnt+1, coin) :
        if j > target_value :
          continue
        if j == target_value :
          return 1
        if not visited[j] :
          visited[j] = True
          next_q.append(j)
    q = next_q
  return 0

for _ in range(3) :
  print(solve())

풀이 완료!