9084 동전 {boj}
다음 블로그 게시글을 참고했습니다.
매 동전마다 한 바퀴 순회를 돌면서 기존의 경우의 수에 '새 동전 coin[i]
이 들어올 자리만큼 뺀 금액'에 대한 경우의 수를 더하는 과정을 갱신해준다.
for i in range(n):
# 동전 i에 대하여
for j in range(coin[i], m + 1):
# 동전 금액 j에 대하여
dp[i][j] += dp[j - coin[i]]
[!Question] 각 동전 i에 대하여 금액 j를 만들었을 때 요구하는 경우의 수를 이전 메모에서 찾는다는 것 까지는 알겠는데, 왜 j의 배수가 아니라 1씩 증가하는거지?