백준, 동전1, 2293, 파이썬

2024. 9. 10. 02:10ETC/Algorithm

[유형]

DP

 

[문제링크]

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

 

[요약]

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

[문제풀이]

for coin in coins: 이전에 사용한 동전은 쓸 수 없다.

dp[4] (1,2원으로 4를 만드는 경우의 수) = dp[4] (원래 1원으로만 4를 만드는 경우의 수) + dp[4-2] (1,2원으로 2를 만드는 경우의 수)

import sys
from collections import Counter
def input():
    return sys.stdin.readline().rstrip()

N, M = map(int, input().split())
coins = []
for _ in range(N):
    coins.append(int(input()))

coins.sort()

dp = [0]*(M+1)
dp[0] = 1
for coin in coins:
    for i in range(coin, M+1):
        dp[i] += dp[i-coin]

print(dp[M])

'ETC > Algorithm' 카테고리의 다른 글

백준, ATM, 11399, 파이썬  (0) 2024.09.10
백준, 동전 2, 22964, 파이썬  (1) 2024.09.10
백준, 동전 0, 11047, 파이썬  (0) 2024.09.10
백준, 입국심사, 3079, 파이썬  (0) 2024.09.06
백준, 나무 자르기, 2805  (0) 2024.09.06