[PS 백준 - 5.3] 2294번: 동전 2

문제 정보

백준 2294번 - 바로가기

• 난이도: 실버 1
• 알고리즘: 다이나믹 프로그래밍

코멘트

이 문제도 DP 블로그의 코드를 그대로 가져와서 풀었다. dp를 처음 접하다보니 아이디어가 꽤 까다롭게 느껴졌던 문제였다.

• [Parameters]
  • n: 동전의 종류 (순서)
  • k: 나타낼 가치
• [base case]
  • 동전을 다 쓰고난 후 나타낼 가치가 0원이면 0 리턴
  • 동전이 다 쓰고난 후 나타낼 가치가 0 초과이면 불가능한 경우이므로 함수에서 나올 수 없는 비정상적인 숫자 리턴
• [Logic]
  1. coin 함수는 n번째 동전부터 사용할 때 k원을 나타내는 동전의 최소 개수를 리턴해야 한다.
  2. n번째 동전 사용이 불가능할 경우 다음 동전을 고려하는 함수로 넘어간다. -> int result = coin(n + 1, k);
  3. n번째 동전 사용이 가능할 경우 결과는 (k를 유지하고 다음 동전으로 넘어간 경우) 와 (k가 감소하고 이 동전을 사용한 경우) 중에서 동전을 최소로 사용한 결과를 리턴하면 된다.

소스 코드

<탑다운 방식>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int cost[101];
int dp[101][10001];
int N;

// n: 동전의 종류 / k: 나타낼 가치
int coin(int n, int k) { // n번째 동전부터만 사용할 때, k원을 나타내는 동전의 최소 개수
	// base case
	if (n == N && k == 0) return 0;
	if (n == N && k > 0) return 100000000; // impossible case
	
	// memoization
	if (dp[n][k] != -1) return dp[n][k];

	int result = coin(n + 1, k);

	// n번째 동전 사용 가능할 경우:
	if (k >= cost[n]) {
		result = min(coin(n + 1, k), coin(n, k - cost[n]) + 1);
	}
	
	// dp 기록 갱신
	dp[n][k] = result;
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int K;
	cin >> N >> K;

	// cost 목록 대입
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		cost[i] = x;
	}

	// memoization을 위한 초기화
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			dp[i][j] = -1;
		}
	}
		
	
	int result = coin(0, K);
	cout << ((result == 100000000) ? -1 : result);
}

<바텀업 방식> - by zzoni

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, K, cost[101], dp[100001];
    cin >> N >> K;

    for (int i = 1; i <= N; i++) cin >> cost[i];
    // dp 배열 초기화
    fill(dp, dp + 100001, 100001);
    dp[0] = 0; //0원

    for (int i = 1; i <= N; i++) {
        for (int j = cost[i]; j <= K; j++) {
            dp[j] = min(dp[j], dp[j - cost[i]] + 1);
        }
    }
    if (dp[K] == 100001) cout << -1;
    else cout << dp[K];

    return 0;
}