G4 2293. 동전 1

문제 보기 :  2293번: 동전 1

---

문제

• 정답률 : 47%

---

작성 코드

n,num = map(int,input().split())
coins = [int(input()) for _ in range(n)]

# num보다 작은 코인만 셀렉
coins = [c for c in coins if c <=num ]

# num원 만드는 경우의 수를 담는 리스트
dd = [0]*(num+1)
dd[0] = 1 #0원 만드는 경우 1개

for coin in coins:
    # [1,0,0,0,...,0]
    for case in range(coin,num+1): 
        dd[case] += dd[case-coin] #dd[1] += dd[0] , dd[2] += dd[1], .. 
        
print(dd[-1])

---

풀이

동적 프로그래밍으로 각 금액을 만드는 방법의 수를 누적 계산하는 방법을 사용했다. dd[x]를 금액 x를 만들 수 있는 경우의 수로 정의한 셈이다.

먼저 dd라는 리스트가 num+1개의 0을 가지도록 정의하고, dp[0] = 1로 초기화했다. (0원을 만드는 방법은 1가지라는 뜻)

그리고 각 동전에 대해, 해당 동전을 사용해 만들 수 있는 금액을 갱신하는데, dp[amount] += dp[amount - coin]으로 현재 금액에서 동전 금액을 뺀 금액을 만드는 경우의 수를 더했다.

DP는 내가 취약한 알고리즘이라 이 문제는 다시 한번 풀이해볼 문제다.