문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 해설 DP를 활용해 푸는 냅색 유형의 문제다. 우선, 우리는 이게 왜 DP 문제인지 생각해보아야 한다. 예를 들어, 1원짜리 동전과 2원짜리 동전이 있다. 이 동전으로 각각 1원, 2원, 3원을 만드는 상황을 생각해보자. 그러면 다음과 같을 것이다. (1원) 동전을 사용하는 경우, (1원/2원) 동전을 사용하는 경우로 나누어 두 줄로 나타내보았다. (1원/2원) 동전을 사용해 3원을 만드는 경우를 들여다보자. 1원을 만드는 방법: 1원짜리 ..