티스토리 뷰
728x90
[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;
}
728x90
'알고리즘' 카테고리의 다른 글
[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 |
댓글