문제우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.해설DP를 활용해 푸는 냅색 유형의 문제다.우선, 우리는 이게 왜 DP 문제인지 생각해보아야 한다. 예를 들어, 1원짜리 동전과 2원짜리 동전이 있다.이 동전으로 각각 1원, 2원, 3원을 만드는 상황을 생각해보자. 그러면 다음과 같을 것이다. (1원) 동전을 사용하는 경우, (1원/2원) 동전을 사용하는 경우로 나누어 두 줄..
