[BOJ/백준] 1943 동전 분배

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
 
max_coins = 50000
for _ in range(3):
    N = int(input())
    coins = defaultdict(int)
    dp = [0 for _ in range(max_coins+1)]
    dp[0] = 1
    total_sum = 0
    for _ in range(N):
        coin,cnts = map(int,input().split())
        for cur_coin in range(max_coins,coin-1,-1):
            if dp[cur_coin - coin]:
                for cnt in range(cnts):
                    next_coin = cur_coin + coin * cnt
                    if 0<=next_coin<=max_coins:
                        dp[next_coin] = 1
        total_sum += coin*cnts
 
    if total_sum%2 or not dp[total_sum//2]:
        print(0)
    else:
        print(1)

이 문제를 풀때 어려움을 많이 겪었다.

 

이 문제를 처음 푼 방식은 다음과 같다. dp는 동전을 만들수 있는 경우의 수이다.

 

먼저 dp[0]은 1로 초기화 해준다.

 

그리고 각 입력이 들어올때마다 dp를 max_coin에서 현재 들어온 동전인 coin 까지 반복문을 돌면서

 

cur_con - coin의 위치에 dp의 값이 존재하면, 만들 수 있는 경우의 수가 있으므로,

 

여기서 부터 다시 동전의 개수만큼 더해주면서 dp를 채워주면 된다.

 

이렇게 dp를 채워준 뒤에 전체 동전을 total_sum에 더해준다.

 

이렇게 한뒤에 만약 홀수 이거나 dp[total_sum//2]의 값이 존재하지 않으면 0을 출력한다.

 

 

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
 
def solution():
    N = int(input())
    coins = []
    total_coins = 0
    for _ in range(N):
        a,b = map(int,input().split())
        coins.append((a,b))
        total_coins += a*b
    if total_coins%2:
        return 0
    else:
        find_coin = total_coins//2
        dp = [0 for _ in range(find_coin+1)]
        dp[0] = 1
        coins.sort(key= lambda x : -x[1])
        acc_coins = 0
        for coin,cnts in coins:
            max_coin = coin*cnts
            for i in range(min(max(acc_coins,max_coin),find_coin),coin-1,-1):
                if dp[i-coin]:
                    for cnt in range(cnts):
                        next_coin = coin*cnt + i
                        if 0<=next_coin<=find_coin:
                            dp[next_coin] = 1
            if dp[find_coin]:
                return 1
            acc_coins += max_coin
        return 0
for _ in range(3):
    print(solution())

 

 

이 풀이는 좀 더 빠르대신 좀 더 복잡하다. 위에서는 고정된 최대값 50000에서부터 하나하나씩 찾는거라 하면,

 

이 풀이는 이 코인에서 가능한 최대값에서부터 하나씩 내려가는 것이다.

 

탐색이 가능한 최대 범위는 acc_coins 누적된 값 아니면 max_coin 중 더 큰 값에서부터 하나씩 내려가야한다.

 

우리는 dp[i - coin] coin 단 1개를 빼서 존재했을때부터 해당 동전이 가지는 개수를 갱신해주기 때문이다.

 

여기서 또 주의해야할 점은 위의 최대값이 find_coin을 넘어갈순 없다. 그러므로 둘중 min값 부터 시작해주면 된다.