동전 1

 

출처 :  https://www.acmicpc.net/problem/2293

 

코드

 

import sys

# 입력
input_data = sys.stdin.read().splitlines()

N, K = map(int, input_data[0].split())
coins = list(map(int, input_data[1:]))
# 테스트용
# N, K = 3, 10
# coins = [1, 2, 5]
dp = [0] * (K + 1)  # dp[i] = i원을 만들 수 있는 조합의 개수
dp[0] = 1  # 0원을 만드는 경우는 아무 동전도 사용하지 않는 경우 1가지

for coin in coins:
    for i in range(coin, K + 1):
        dp[i] += dp[i - coin]  # 현재 금액에서 coin을 더해 만들 수 있는 경우 추가
    
print(dp[K])

 

 

풀이

 

0부터 K 까지의 리스트를 만들고

 

각 숫자를 만들 수 있는 경우를 더해간다

 

모든 경우를 구한 후 K를 만들 수 있는 경우를 반환한다.

 

주의, 조합을 하려는 경우 메모리 터짐 ⇒ 되나 했봤는데 역시 안 됨.

 

경우의 수가 너무 많기 때문에 메모리가 터짐

 

 

 

다음에 또 봐요