동전1
-
[알고리즘] 백준 - 2293. 동전1알고리즘 2023. 2. 1. 15:26
1. 문제 2. 접근 - 이 문제는 이코테의 효율적인 화폐 구성과 유사하다. N가지의 화폐로 K원을 만족시키는 경우의 수를 구하는 DP 문제임을 알 수 있다 - 각 숫자를 (1,2,5)를 더해서 숫자를 나타내는 방법을 표로 경우의 수를 확인할 수 있다. 3. 풀이 # 골드5 - 2293 import sys input = sys.stdin.readline n, k = map(int, input().split()) coin = [] for i in range(n): coin.append(int(input())) d = [0] * (k+1) d[0] = 1 for i in coin: for j in range(1, k+1): if j - i >= 0: d[j] += d[j-i] print(d[k])