[C++] 백준 2293번 동전1

 

다이나믹 프로그래밍 문제입니다.

 

1부터 n까지 차례대로 진행하며

현재 위치의 저장값에 검사하고 있는 코인만큼 인덱스를 뺀 위치의 값을 더해줍니다.

 

=>

for (int k = 0; k < coinNum; ++k) {
 	for (int j = coin[k]; j <= findCoin; ++j) {
 		memo[j] += memo[j - coin[k]];
 	}
}

 

#include <iostream>
using namespace std;

int memo[10010];
int coin[10010];


void init()
{
   for (int i = 0; i < 10010; ++i) {
      memo[i] = 0;
      coin[i] = 0;
   }
}

int main(int argc, char *argv[])
{
   init();
   int coinNum = 0;
   int findCoin;
   memo[0] = 1;
   cin >> coinNum;
   cin >> findCoin;
   for (int j = 0; j < coinNum; ++j) {
      cin >> coin[j];
   }
   for (int k = 0; k < coinNum; ++k) {
      for (int j = coin[k]; j <= findCoin; ++j) {
         memo[j] += memo[j - coin[k]];
      }
   }
   cout << memo[findCoin] << endl;
   return 0;
}