[백준 1943 🥇] 동전 분배

문제

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

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

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

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

입력

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

출력

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

문제풀이

import sys

for _ in range(3):
    n=int(sys.stdin.readline())
    coins=[]
    amount=0
    for _ in range(n):
        coin, num=map(int, sys.stdin.readline().strip().split(' '))
        coins.append([coin, num])
        amount+=coin*num
    # 총액이 홀수이면 똑같이 분배할 수 없으므로 0 출력하고 종료
    if amount%2==1:
        print(0)
        continue
    goal=amount//2
    dp=[1]+[0]*(goal)
    for coin, num in coins:
        for n in range(goal,coin-1, -1):
            if dp[n-coin]==1:
                for i in range(num):
                    if n+coin*i<=goal:
                        dp[n+coin*i]=1
                    else:
                        break
    if dp[-1]==1:
        print(1)
    else:
        print(0)

• 냅색 알고리즘을 사용하는 문제였다.
  • 이해됐다 싶다가도 다시 보면 또 잘 이해가 안된다.. 완벽하게 이해한 게 아닌 거 같다. 냅색 알고리즘을 제대로 파고 들어서 냅색만 따로 포스팅해야겠다!
• 동전과 동전 개수를 입력받으면서 총액을 계산해주는데 이때 총액이 홀수라면 둘로 똑같이 나눠지진 못하기 때문에 0을 출력하고 넘어가면 된다.
• 총액이 짝수라면 DP를 이용해서 DP[총액//2] 값이 1인지, 즉 가지고 있는 동전들로 총액//2 값을 만들 수 있는지 확인한다.
• 여기서 dp[n]의 의미는 가지고 있는 동전들로 n원을 나타낼 수 있는지(1), 없는지(0)를 의미한다.
• 먼저 DP 배열을 선언할 때 DP[0]은 1로 초기화해준다. (아무것도 안 내도 지불 가능하니까) 그리고 나머지 값들은 0으로 초기화해준다.
• 입력받은 동전(coin)과 각 동전의 개수(num)를 순차적으로 탐색하면서 DP 값을 채워준다.
• 변수 goal에 저장된 총액//2 값부터, 현재 탐색 중인 coin까지 for문으로 탐색하면서 dp[n-coin]이 만들 수 있는 값인지(1) 확인한다.
• 즉, 'n-coin'이 만들 수 있는 값이라면(dp[n-coin]) 우리는 현재 coin을 가지고 있기 때문에 n 또한 우리가 만들 수 있는 수가 된다.
  • 이제 coin의 개수(num)-1만큼 for문을 돌면서 만들 수 있는 값을 dp에 갱신해준다.
  • coin 1개를 이용하면 n은 만들 수 있는 수가 되기 때문에 coin의 개수가 남는 한 n+coin*1, n+coin*2,..,n+coin*(num-1)도 goal을 초과하지 않으면 만들 수 있는 수가 된다.
• 이 과정을 반복해서 모든 동전을 탐색하고 나서, dp의 마지막 값 즉, dp[총액//2] 값이 1이라면 반으로 나눌 수 있다는 뜻이므로 1을 출력하고 그렇지 않다면 0을 출력한다.