[백준] 동전 분배

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

1943번: 동전 분배

정말 이 문제가 어떻게 골드3 문제인지 이해가 안되는 문제였습니다. 처음에는 그리디로 접근을 했습니다. 모든 동전의 개수를 짝수로 맞춰주면 된다고 생각을 했고 동전의 가격을 내림차순으로 정렬하여 가격이 큰 동전의 개수를 짝수개로 먼저 맞춰주면서 내려오는 풀이법을 생각했는데 가격의 큰 동전의 가격에 맞게 조합을 짤 경우의 수가 너무 많다고 하여 포기하였습니다.

 

그래서 알고리즘 분류를 보았는데 DP와 배낭 문제였습니다. 이를 확인하고는 2차원 냅색으로 풀이했지만 시간초과가 발생했고 dp의 가로를 총합 가격의 절반으로 줄였어도 시간초과가 났습니다. 수많은 삽질 끝에 1차원 냅색 + 가격의 역방향 순서로 dp배열을 채우는 방식으로 수정하여 간신히 pypy로 통과하였습니다.

 

수많은 시간 초과와 틀렸습니다..

 

import sys

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

for t in range(3):
    n = int(input())
    sum_of_coin = 0
    cnt_of_cnt = 0

    coins = [(-1, -1)]


    for _ in range(n):
        price, cnt = tuple(map(int, input().split()))
        coins.append((price, cnt))
        sum_of_coin += price * cnt
        cnt_of_cnt += cnt


    # 총 금액의 합이 홀수이면 절반으로 나눌 수 없다.
    if sum_of_coin % 2:
        print(0)
        continue

    half_of_coin = sum_of_coin // 2

    dp = [False] * (half_of_coin + 1)

    # 0원은 항상 만들 수 있다.
    for i in range(n + 1):
        dp[0] = True

    flag = False
    for i in range(1, n + 1):
        price, cnt = coins[i]
        for j in range(half_of_coin, 0, -1):
            for k in range(1, cnt + 1):
                if j - price * k >= 0:
                    if dp[j - price * k]:
                        dp[j] = True
                        break
                if dp[half_of_coin]:
                    break

        if dp[half_of_coin]:
            flag = True
            break


    if flag:
        print(1)
    else:
        print(0)