문제 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 분류된 문제로 간단한 메모이제이션을 통해 풀이가 가능. 접근법 입력으로 주어진 동전으로 목표가치 K를 만드는 최소 개수를 구하는 문제로 DP문제인 만큼 Sub Problem을 찾으려 했음. Sub Problem : 각각의 동전으로 1원부터 목표(K)까지의 가치를 만들기위한 사용한 동전의 최소개수 부분 문제를 찾았으니 먼저 해야할 것은 부분 해를 저장할 dp배열을 선언하는 것...