728x90
https://www.acmicpc.net/problem/2293
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
최근에 DP를 배우고 DP문제에 재미들렸다. DP가 유독 생각하는 시간이 코드 수정하는 시간보다 많은 알고리즘인 것 같다. DP 코드가 대체적으로 길지 않은데 어렵다보니 매력적인 알고리즘이다.
이 동전 문제도 DP문제 중 대표적인 유형이라고 볼 수 있을 것 같다. 이전에 공부했던 내용이라 금방 풀었음.
n,k=map(int,input().split())
coins = []
for _ in range(n):
coins.append(int(input()))
dp = [0]*(k+1)
dp[0] = 1
for coin in coins:
for j in range(coin, k+1):
dp[j] = dp[j] + dp[j-coin]
print(dp[k])728x90
'알고리즘 > DP' 카테고리의 다른 글
| [Python] 백준 1520 - 내리막 길 (0) | 2023.01.30 |
|---|---|
| [Python] 백준 9456 - 스티커 (0) | 2023.01.29 |
| [Python] 백준 1890 - 점프 (0) | 2023.01.28 |
| [Python] 백준 12852 - 1로 만들기 2 (0) | 2023.01.21 |
| [Python] 백준 2294 - 동전 2 (0) | 2023.01.19 |