[python] 백준 1943 동전 분배

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

1943번: 동전 분배

 

문제 해결

• 먼저 돈의 총 합을 보았을 때 홀수이면 나눌 수 없다는 것을 알 수 있다.
• 짝수여도 무조건 가능한 것은 아니지만 총합의 절반을 나눌 수 있다.
• 절반을 가지고 가지고 있는 동전을 조합하여 맞출 수 있는가?를 보면 된다.
  • 이는 DP를 가지고 풀 수 있다.
  • 처음에는 이론상 0원만 가능하고 동전의 종류별로 채워나가며 dp[total]이 True가 된다면 만들 수 있는 것이다.
  • 만약 모든 경우 다 해봤는데 불가능하면 불가능 한 것이다.

CODE

import sys
input = sys.stdin.readline

def Bool(total):
    if total%2:
        return True
    return False

if __name__=='__main__':
    for _ in range(3):
        n = int(input())
        total = 0
        coins = []
        for _ in range(n):
            val, num = map(int, input().split())
            total += val*num
            coins.append([val, num])

        if Bool(total):
            print(0)
            continue
        total //= 2 # 절반만 확인
        dp = [True] + [False]*total

        answer = 0
        for i in range(len(coins)):
            val, num = coins[i]
            for k in range(total, val-1,-1):
                if dp[k-val]:
                    for j in range(num):
                        if k + val*j <= total:
                            dp[k+val*j]=True
                        else:break
            if dp[-1]: # 절반만큼 귀납적으로 값을 만들었다는 말. 나머지 동전은 다른 친구한테 주면 절반씩 나눠가지는 것이 됨
                answer = 1
                break
        print(answer)