[DP] changeCoin?

[DP] changeCoin?

예제: https://www.acmicpc.net/problem/2293

// 동전교환
// 동전 갯수, 목표금액
// 동전 종류들

// [만들고 싶은 금액 - 현재 동전의 값] => 가지수
// +
// [만들고 싶은 금액] => 가지수

#include <iostream>
#include <string.h>
using namespace std;

#define COIN_COUNT 100
#define SIZE 10001

int main() {
   int coin[COIN_COUNT];

   int coinCount, target;
   cin >> coinCount >> target;

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

   int dp[SIZE];
   memset(dp, 0, sizeof(dp));

   dp[0]=1;
   for(int i=0; i<coinCount; i++) {
      for(int j=coin[i]; j<=target; j++) {
         dp[j] += dp[j - coin[i]];
      }
   }

   cout << dp[target] << endl;

   return 0;
}

예제: https://www.acmicpc.net/problem/2294

// 동전교환
// 동전 갯수, 목표금액
// 동전 종류들

// dp 항목 중요 동전의 갯수 이므로 0로 초기화하고
// 점화식에 기존 동전 + 1로한다.
// 0x7fffffff == INF
// memset 은 0x7f 만 가능하므로 주의하자

#include <iostream>
#include <string.h>
using namespace std;

#define COIN_COUNT 100
#define SIZE 10001
#define INF 0x7fffffff

int main() {
   int coin[COIN_COUNT];

   int coinCount, target;
   cin >> coinCount >> target;

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

   int dp[SIZE];
   for(int i=0; i<=target; i++) {
      dp[i] = INF;
   }

   dp[0] = 0;
   for(int i=0; i<coinCount; i++) {
      for(int j=coin[i]; j<=target; j++) {
         if(dp[j - coin[i]] != INF && dp[j] > dp[j - coin[i]] + 1) {
            dp[j] = dp[j - coin[i]] + 1;
         }
      }
   }
   int result = (dp[target] == INF) ? -1 : dp[target];
   cout << result << endl;

   return 0;
}