CodeAngie

문제주어진 금액을 만들기 위해 동전 종류에 따라 거스름돈을 주는 방법의 수를 구하는 문제이다.풀이동적 프로그래밍(DP)을 사용해 풀 수 있다. 특정 금액 n을 만들기 위한 방법의 수를 누적해서 계산한다. 이때 작은 동전(금액)부터 시작해 큰 동전에 대해 가능한 경우의 수를 차례로 계산한다. dp[0]은 항상 아무 동전도 쓰이지 않는 방법 한 가지만 존재함으로 dp[0]=1로 지정한다. 현재 금액 x를 만들기 위한 방법의 수는 x - coin을 만들 수 있는 방법의 수에 현재 동전 coin을 추가한 것이다. 이를 토대로 점화식을 구성하면 dp[x] = dp[x] + dp[x-coin] 이 된다. 마지막 정답을 도출할 때는 숫자가 매우 커질 것을 방지해 1000000007로 나눈 나머지를 반환한다.Pytho..