3067: Coins

문제 보기
배낭 문제(Knapsack Problem)은 DP를 이용하는 유명한 문제이다.
$dp_k = dp_{k-c_1}+dp_{k-c_2}+\cdots$ (단$, {c_i\in coins}$이고$, i<0$ 에 대해 $dp_i=0$)

이 작업을 $O(n+m)$의 메모리 내에서 구현하는 것은 매우 까다롭다.
까다로운 정도가 아니라 일반적으로 불가능하다.

왜냐하면 $c_1<c_2<\cdots <c_n$을 만족하는 경우에만 다음의 트릭을 이용하는 것이 가능하기 때문이다.
이 트릭이 무엇이냐 하면, 배열을 1차원으로 만들어서
+= 연산자를 이용하는 것이다.