-문제
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
-풀이
dp 리스트를 (k+1) 크기만큼으로 선언한다.
동전의 값 coin와 만들고자 하는 금액인 i 사이에는 아래와 같은 관계식이 성립한다.
dp[i] += dp[i-coin]
단, i == coin일 경우에는 coin 하나로 i를 생성할 수 있기에 1을 더해준다.
-소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
input = sys.stdin.readline
coins = []
n, k = map(int, input().split())
for _ in range(n):
coins.append(int(input()))
coins.sort()
dp = [0] * (k+1)
for coin in coins:
for i in range(coin, k+1):
if coin == i:
dp[i] += dp[i-coin] +1
else:
dp[i] += dp[i-coin]
print(dp[-1])
|
cs |
'백준 문제 풀이 Python' 카테고리의 다른 글
| [백준/Python] 11057번 오르막 수 (0) | 2022.11.30 |
|---|---|
| [백준/Python] 11055번 가장 큰 증가 부분 수열 (2) | 2022.11.29 |
| [백준/Python] 15486번 퇴사2 (0) | 2022.11.28 |
| [백준/Python] 9205번: 맥주 마시면서 걸어가기 (0) | 2022.11.27 |
| [백준/Python] 2573번: 빙산 (0) | 2022.11.26 |