[성실코딩 32일차] 백준 #2294 동전 2 / Knapsack

기말고사 준비로 Knapsack Problem 문제만 골라서 풀고 있다.

이 문제는 Unbounded Knapsack Problem으로 분류할 수 있고 

내가 냅색을 공부할 때 예제로 봤던 문제와의 차이점은 

배낭 안의 물건들의 무게의 합이 배낭이 최대 수용할 수 있는 무게와 같지 않으면 

불가능으로 처리하고 -1을 반환해야하는 것이다

따라서 '배낭 안의 물건들의 무게의 합 == 배낭의 무게' 를 확인하기 위하여

findMaximumValue 함수에서

if( products[i].weight <= _c ) 이 부분을 아래와 같이 수정해줬다.

if( products[i].weight <= _c && _m[_c-products[i].weight]!= -1 ) 

문제 풀이

문제 정의와 필요한 변수(전역변수)

손코딩

DP Table을 채웠을 때 값

C언어 구현코드 (C++아님)

#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset

#define INF 987654321

int n, k; // 동전의 개수n, 금액k

int coins[101];
int DP[10001] = { 0, };

// _k : 채워야하는 금액
int getMinimumCoinCnt(int _k) { 
	int minimum = INF;
	for (int i = 0; i < n; i++) { // 동전의 개수만큼 확인 ( 모든 동전 다 확인)
		int new_cnt = INF;
		if (coins[i] <= _k                   // i번째 동전 <= 채워야하는 전체 금액 _k
			&& DP[_k - coins[i]] != -1) {    // && 나머지 금액이 코인으로 만들어질 수 있는 금액이라면
			new_cnt = DP[_k - coins[i]] + 1;
			if (minimum > new_cnt) {  // 가장 작은 값으로 update
				minimum = new_cnt;
			}
		}
	}
	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;
}