[BOJ/백준] 2624 동전 바꿔주기

# 입력 지폐의 금액 T 동전의 가지수 k 각 동전 하나의 금액 pi ni가 주어진다.
# 방법의 수는 2^31 -1 을 초과하지 않는다.



T = int(input())

k = int(input())

money = [list(map(int,input().split())) for _ in range(k)]

money.sort(reverse=True)
dp = (T+1)*[0]

dp[0] = 1
for coin_val,coin_cnt in money:
    for current_money in range(T,1,-1):
        for current_cnt in range(1,coin_cnt+1):
            if current_money - current_cnt*coin_val >= 0:
                dp[current_money] += dp[current_money-current_cnt*coin_val]
print(dp[T])

DP 관련 문제였다. 풀고보니 평범한 배낭과 비슷한 로직이었다. 거기서는 가치를 판단하여, 가치값의 최대를 찾는거였다면, 여기는 방법의 가지수를 찾는 것이라 다르지만, 하나의 dp를 이용해 역으로 진행하면서, 누적시켜주는 것에 있어서 비슷하다고 봤다.

 

기본적이 원리는 다음과 같다.

동전의 가지수 k개가 주어지면,

첫번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어 본다.

그리고 두번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어서 누적시켜준다.

이렇게 k번을 반복을 해준다.

여기서 주의해야할 점은 아래에서 위로 올라가면, 이전에 만들어진 것 때문에, 원치 않는 결과가 나올 수 있으므로,

주어진 목표 금액인 T에서 -1씩 줄여주면서 다이나믹 프로그래밍을 해준다.

여기서 평범한 배낭과 또 다른 점은, 같은 동전이 여러개 존재하는 것이다.

그래서 동전의 개수 n개만큼 반복을 시켜주면서 진행해야한다.

즉 3원짜리 동전이 5개가 있다하면,

1회차   // 2회차

T - 3*1 ,| (T-1) - 3*1, ....

T - 3*2, |(T-1) - 3*2 ,...

T - 3*3, |(T-1) - 3*3, ...

T- 3*4,  |(T-1) - 3*4 .....

T - 3*5, |(T-1) - 3*5 ....

 

이렇듯 동전의 개수만큼 진행시켜줘야, 그 동전으로 만들 수 있는 모든 경우를 탐색할 수 있다.

여기서 또 주의해야할 점은 T는 동전의 개수를 조정하는 반복문 밖에 있어야한다.

 

원래 DP에 약하기도 했지만 비슷한 문제를 풀어본 경험이 있었는데도, 푸는데 시간이 오래걸렸다.

이전에 풀었던 문제들도 다시 공부하여, DP에서 필요한 점화식을 빨리 구하는데 노력해야겠다.