[백준]2624 동전바꿔주기 #경우의 수

1. 풀이

dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수.

기본적으로 무제한 동전dp(https://blog.naver.com/ngoodsamari/221664277387)와 같지만 사용할 수 있는 동전의 개수 제한이 추가된 문제이다.

무제한 동전 dp문제와 리스트형식은 같지만 푸는 방법이 전혀 다르다.

​

(1) 1번째부터 k번째까지 사용할 수 있는 동전을 하나씩 늘려간다

(2) i번쨰 동전을 사용할때는 i-1번째 동전까지 사용한 경우의 수에서 i번째 동전을 최대 사용가능한만큼 하나씩 늘려가며 확인한다.

(3) i번째 동전까지 사용하여 0원을 만드는 경우는 1임을 주의한다. (무제한 동전dp와 같다)

​

2.소스코드

T=int(input())
k=int(input())
L=[[0,0]] #[금액,동전가지수]
for i in range(k):
    L.append(list(map(int,input().split())))
L.sort()
dp=[[0 for j in range(T+1)] for i in range(k+1)]
for i in range(k+1):
    dp[i][0]=1

# i번째 동전까지 사용
for i in range(1,k+1):
    #print(L[i],"금액,가용개수")
    # i번째 동전을 num번 사용
    for num in range(L[i][1]+1):
        #print(num,"번사용했을떄")
        for j in range(T+1):
            temp=j+num*L[i][0]
            if temp==0:
                continue
            if temp<T+1:
                dp[i][temp]+=dp[i-1][j]
            else:
                break

print(dp[k][T])