반응형
기말고사 준비로 Knapsack 문제만 풀고 싶었는데,,,
이건 그리드알고리즘을 이용해서 푸는 문제라고 한다.
그 이유가 되는 단서는 문제에서,
(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
이러한 조건을 줬기때문에 그리디 알고리즘을 이용해서 푼다고 한다.
막 나누고 어떻게 하던데,, 기말 끝나고 시도해봐야겠다.
나는 Knapsack으로 풀어서 모두 메모리 초과가 났다 ㅠㅠ
1풀이법. 재귀적으로
#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset
#define INF 987654321
int n, k; // 동전의 개수n, 금액k
int coins[11];
// _k : 채워야하는 금액
// 2차원 배열 사용 안하고 재귀적으로 구하기
int getMinimumCoinCnt(int _k) {
if (_k==0) { // 탈출조건
return 0;
}
int minimum = INF;
for (int i = 0; i < n; i++) { // n: 동전 개수
int new_value = INF;
if (coins[i] <= _k) {
int temp = getMinimumCoinCnt(_k - coins[i]);
if (temp != -1) { // -1이 아니라는 것은
// 동전 i를 사용해서 금액 _k를 만들 수 있다.
new_value = temp + 1;
if (minimum > new_value) { // minimum update
minimum = new_value;
}
}
}
}
if (minimum == INF) { // 불가능한 경우
// 내가 가진 코인들을 이용해서 금액 _k를 만들 수 없음.
return -1;
}
else {
return minimum;
}
}
int main(void) {
// 입력
scanf("%d %d",&n,&k);
for (int i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
printf("%d\n", getMinimumCoinCnt(k));
return 0;
}
1-1 풀이법. 재귀적으로 + k금액을 이룰수 있는 경우, 거기서 반복문을 멈춘다.
-> 왜 다른 코인을 사용한 경우를 확인해주지 않아도 되는지 모르겠음.
어차피 문제에서 코인을 줄 때 오름차순으로 주기 때문인가?
#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset
#define INF 987654321
int n, k; // 동전의 개수n, 금액k
int coins[11];
// _k : 채워야하는 금액
// 2차원 배열 사용 안하고 재귀적으로 구하기
int getMinimumCoinCnt(int _k) {
if (_k==0) { // 탈출조건
return 0;
}
int minimum = INF;
for (int i = n-1; i > -1; i--) { // n: 동전 개수
int new_value = INF;
if (coins[i] <= _k) {
int temp = getMinimumCoinCnt(_k - coins[i]);
if (temp != -1) { // -1이 아니라는 것은
// 동전 i를 사용해서 금액 _k를 만들 수 있다.
new_value = temp + 1;
if (minimum > new_value) { // minimum update
minimum = new_value;
break;
}
}
}
}
if (minimum == INF) { // 불가능한 경우
// 내가 가진 코인들을 이용해서 금액 _k를 만들 수 없음.
return -1;
}
else {
return minimum;
}
}
int main(void) {
// 입력
scanf("%d %d",&n,&k);
for (int i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
printf("%d\n", getMinimumCoinCnt(k));
return 0;
}
2풀이법. 1차원 array를 만들어서 DP Table을 채워가며
#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset
#define INF 987654321
int n, k; // 동전의 개수n, 금액k
int coins[11];
int DP[100000001] = { 0, };
// _k : 채워야하는 금액
// 2차원 배열 사용 안하고 재귀적으로 구하기
int getMinimumCoinCnt(int _k) {
int minimum = INF;
for (int i = 0; i < n; i++) { // n: 동전 개수
int new_value = INF;
if (coins[i] <= _k && DP[_k-coins[i]]!=-1) { // -1이 아니라는 것은
// 동전 i를 사용해서 금액 _k를 만들 수 있다.
new_value = DP[_k - coins[i]] + 1;
if (minimum > new_value) { // minimum update
minimum = new_value;
}
}
}
if (minimum == INF) { // 불가능한 경우
// 내가 가진 코인들을 이용해서 금액 _k를 만들 수 없음.
return -1;
}
else {
return minimum;
}
}
int main(void) {
// 입력
scanf("%d %d",&n,&k);
for (int i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
// DP Table채우기
DP[0] = 0;
for (int i = 1; i <= k; i++) {
DP[i] = getMinimumCoinCnt(i);
}
printf("%d\n", DP[k]);
return 0;
}
2-1 풀이법. 1차원 array + k금액을 이룰 수 있는 경우, 거기서 반복문을 멈춘다. (모든 코인을 확인해보지 않아도 된다.)
이것도 1-1풀이법과 같은 이유로 왜 가능한지 의문이다.
#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset
#define INF 987654321
int n, k; // 동전의 개수n, 금액k
int coins[11];
int DP[100000001] = { 0, };
// _k : 채워야하는 금액
// 2차원 배열 사용 안하고 재귀적으로 구하기
int getMinimumCoinCnt(int _k) {
int minimum = INF;
for (int i = n-1; i > -1; i--) { // n: 동전 개수
int new_value = INF;
if (coins[i] <= _k && DP[_k-coins[i]]!=-1) { // -1이 아니라는 것은
// 동전 i를 사용해서 금액 _k를 만들 수 있다.
new_value = DP[_k - coins[i]] + 1;
if (minimum > new_value) { // minimum update
minimum = new_value;
break;
}
}
}
if (minimum == INF) { // 불가능한 경우
// 내가 가진 코인들을 이용해서 금액 _k를 만들 수 없음.
return -1;
}
else {
return minimum;
}
}
int main(void) {
// 입력
scanf("%d %d",&n,&k);
for (int i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
// DP Table채우기
DP[0] = 0;
for (int i = 1; i <= k; i++) {
DP[i] = getMinimumCoinCnt(i);
}
printf("%d\n", DP[k]);
return 0;
}
=> 재귀적으로 푸는 건 함수 타고 들어가면서 heap 메모리에서 stackoverflow 문제가 발생했고
DP Table 채워가며 푸는 건 전역변수로 1억개를 할당해서 data 메모리에서 메모리 초과가 난 것 같다.'
=> 기말 끝나고 그리디로 다시 풀어봐야겠다.
반응형
