파이썬 백준 9084번 : 동전

문제 

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

 

 

🪙풀이

DP로 풀었다.

DP table인 coin_list는 해당 동전이 없었을때  만들수 있는 경우의 수와 만들고자 하는 돈에서 해당동전을 뺐을때 만들수있는 경우의 수의 합이다! 

 

예를 들어 2와 5 동전으로 10을 만들고자 할 때,

7을 보면, 2와 5로 7을 만들 수 있는 경우는 2로만 만들수있는 경우(0) + 7-5=2 를 만들 수 있는 경우(1) 의 합이다. 

(이때 2와 5로 2를 만들 수 있는 경우의 수는 마찬가지로 2로만 2를만들 수 있는경우의 수(1) + 5로 만들수 있는경우의수 (0)의 합이다)

 

마찬가지로 10은 2로만 10을만들수 있는 경우(1) + 10-5를 만들수 있는 경우의수 (1) 이다!  

import sys

T=int(sys.stdin.readline())
for _ in range(T):
    N=int(sys.stdin.readline())
    coin=list(map(int,sys.stdin.readline().split()))
    M=int(sys.stdin.readline())
    
    while(coin): #coin이 만들어야하는 M보다 큰 경우 제거
        if coin[-1]<=M:
            break
        if coin[-1]>M:
            coin.pop()
            
    coin_list=[[0]*(M+1)]
    for _ in range(len(coin)):
        coin_list.append([0]*(M+1))
    coin_list[0][0]=1 #0은 무조건 1

    for i in range(1,len(coin_list)):
        coin_list[i][0]=1
        for j in range(M+1):
            coin_list[i][j]=coin_list[i][j-coin[i-1]]+coin_list[i-1][j]

    if len(coin)>0:
        print(coin_list[i][j])
    else:
        print(0)

 

 

 

 

🥲덧)

처음에 런타임 에러가 발생했는데, 동전이 M보다큰경우를 고려하지 않아서였다.

반례는 아래와 같다.

1
2
1 10000
1000

1
2
5000 10000
1000