티스토리 뷰

알고리즘

[DP] changeCoin?

seunggabi 승가비 2018. 9. 8. 23:52

[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;
}


'알고리즘' 카테고리의 다른 글

[DataStructure] Queue?  (0) 2018.09.13
[Sort] QuickSort  (0) 2018.09.11
[DP] changeCoin?  (0) 2018.09.08
[Greedy] jewelryThief - priority_queue(heap)  (0) 2018.09.08
[Math] changeProposition?  (0) 2018.09.08
[Graph] Floyd Warshall?  (0) 2018.09.08
댓글
댓글쓰기 폼