문제
동전의 종류가 주어진다. 동전은 1~10000 사이의 값을 갖는다. 숫자 M이 주어질 때 동전으로 M을 만들 수 있는 경우의 수를 구하여라.
풀이
DP는 그냥 여러 유형을 익히는 수 밖에 없는 것 같다. 풀이를 보고 풀었다.
dp table을 1~M 까지 만들고 각 coin에 대해서 순서대로 coin~M 까지의 dp table을 초기화한다. 초기화 하는 방법은 다음과 같다.
if i == coin:
dp[coin] += 1
if i > coin:
dp[i] += dp[i-coin]
그럼 n번째 coin까지 진행하면서 dp table은 모든 coin에 대해 초기화된다.