[C++] 백준 2294번 동전 2

 

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

 

n개의 동전을 가지고 k원을 만들때

최소한의 동전의 개수를 구하는 문제입니다.

 

작은 동전부터 큰 동전 순으로 1~k원을 구할때 드는 동전 수를 구합니다.

그리고 만약 이미 값을 저장한 곳에 값이 있으면 현재 동전의 수가 더 작으면 값을 변경해줍니다.

이를 코드로 하면 이와 같습니다.

memo[j] = min(memo[j], memo[j - coin[i]] + 1);

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
   int coinNum;
   int findCoin;
   int coin[10010] = { 0, };
   int memo[100010] = { 0, };
   cin >> coinNum;
   cin >> findCoin;

   for (int i = 1; i <= coinNum; ++i) {
      cin >> coin[i];
   }

   for (int i = 1; i <= coinNum; ++i) {
      int j = coin[i] + 1;
      memo[coin[i]] = 1;
      for (; j <= findCoin; ++j){
         if (memo[j - coin[i]] == 0) {
            continue;
         }
         if (memo[j] == 0) {
            memo[j] = memo[j - coin[i]] + 1;
         }
         memo[j] = min(memo[j], memo[j - coin[i]] + 1); 
      }
   }
   if (memo[findCoin] == 0) {
      cout << "-1" << endl;
   }
   else {
      cout << memo[findCoin] << endl;
   }

   return 0;
}