백준, 동전1, 2293, 파이썬
2024. 9. 10. 02:10ㆍETC/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 |