백준 문제 풀이 Python
[백준] 2293번 동전 1 - 파이썬[Python]
골슼
2022. 12. 12. 22:16
-문제
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 |