백준 dp c++

[baekjoon 2294] 동전 2- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 주어진 동전의 값을 이용해서 목표한 값을 동전 개수의 합으로 나타내는 경우 중 최소한의 동전 개수를 출력한다. 동전의 값보다 작은 숫자는 만들지 못한다. 동전의 값보다 큰 숫자는 크기가 n인 동전으로 구성할 수 있다. 그리고 그 이후에 크기가 n보다 큰 동전으로 그 숫자를 구성할 수 있다면 동전의 개수는 줄어든다. 즉, 5를 동전 1, 2, 5로 만들 수 있는 경우를 생각해보면 동..