Coin Change

문제 : http://algospot.com/problems/read/COINS


접근 방법
알고리즘 수업시간에 배웠던 내용이고, 공부했던 기억이 분명히 있었는데 한참을 떠올리려 고민하다가, 결국 강의자료 앞부분을 보고 점화식을 만들어 풀었다 ...;; 그때는 이해를하지 않고 암기를 해서 풀었나보다 (반성)ㅠ

잔돈의 종류가 n개로  k원의 거스름돈을 주는 가지수를 Coin(n, k)라고 하면,
임의의 잔돈 Cn이 포함된 경우 + 동전 Cn이 포함되지 않는 경우로 나눌 수 있다.

전자의 경우 Coin(n, k-Cn)
후자의 경우 Coin(n-1, k)
따라서 Coin(n, k) = Coin(n, k-Cn) + Coin(n-1, k)


발전적 제언.
k개 만큼의 배열을 선언하는데, 몇만원을 거슬러주는 경우 상당히 큰 배열을 필요로 하기때문에 메모리 초과현상이 나타날 수 있다. 이를 해결하기 위한 테크닉이 필요할 것 같다.
(물론 위 문제에서는 Cover 가능한 범위에서 Constraint되어 있다.)

#define REP(i,n) for((i)=0; (i)<(int)(n); (i)++)
// 초항 대입
  REP(i, numOfCoin+1) dp[i][0]=1;
  REP(i, change+1) dp[0][i]=0;
  //DP table 계산
  for(i=1; i<numOfCoin+1; i++)
  {
   for(int j=1; j<change+1; j++)
   {
    if(j-coins[i-1] < 0)
     dp[i][j] = dp[i-1][j];
    else
     dp[i][j] = (dp[i][j-coins[i-1]]+dp[i-1][j])%1000000007;
   }
  }