흙금이네 블로그

아이디어 동적 계획법으로 각 동전을 사용한 교환 방법의 가짓수를 저장해 나간다. 풀이 #1 (Python) 0으로 채워진 T+1 크기의 리스트 dp를 생성하는데, dp[i]에는 i원의 교환 방법 가짓수를 저장한다. for문에서 동전의 금액 p와 동전 개수 n을 입력 받고, temp에 리스트 dp를 복사하여 저장한다. p원 동전으로만 교환하는 방법의 가짓수는 1이므로 n 이하의 자연수 i에 대해 dp[p*i]를 1씩 증가시킨다. p원 동전을 사용하여 교환하는 방법의 수는 그 금액보다 p원만큼 작은 금액을 기존 동전들로 교환하는 방법의 수와 같다. 따라서 기존 동전들과 함께 사용하여 교환하는 방법의 수 dp[j]에 기존 동전들로만 교환하는 방법의 수 dp[j-p*i]를 더한다. 지폐의 금액 T를 넘는 동전의..