BOJ - 동전 2(2294)

실버1 : 동적 계획법 문제이다.

생각

다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.

정의

dp[i] = n의 가치를 만들기 위해 필요한 최소 숫자의 개수

정의는 매우 간단하다. 하지만 이 것을 구현할 때는 2차원 처럼 생각해야 편하다.

점화식

dp[j] = min(dp[j],dp[j-a[i]]+1)

위의 점화식이 나오는 과정을 생각해보자.

3 15
2
5
10

========동전의 값 : 2========
0 - 1 - 2 - 3 - 4 - 5 - 6 - 7

========동전의 값 : 5========
0 - 1 - 2 1 3 2 4 3 2 4 3 5 4

========동전의 값 : 10========
0 - 1 - 2 1 3 2 4 3 1 4 2 5 3

1. 2로써 만들 수 있는 것을 업데이트 한다.
2. 5로써 만들 수 있는 것을 업데이트 한다.
3. 10로써 만들 수 있는 것을 업데이트 한다.

이 때, 해당 가치가 업데이트 되는 방향은 결정되어 있다. 5의 가치는 3의 가치에서 2의 동전을 더해서 만들 수 있다. 이런 관계를 잘 엮는다면 문제를 해결할 수 있다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N, M;
int a[101];
int dp[10001];
const int INF = 987654321;
 
void print(int coin){
    cout << "========" << "동전의 값 : "<< coin << "========" << '\n';
    for (int i = 0; i < M; i++) {
        if (dp[i] == INF) {
            cout << '-' << " ";
        } else cout << dp[i] << " ";
    }cout << '\n' << '\n';
}
 
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
 
    fill(dp+1, dp+M+1, INF);
 
    for (int i = 1; i <= N; i++) {
        for (int j = a[i]; j <= M; j++) {
            dp[j] = min(dp[j],dp[j-a[i]]+1);
        }
        print(a[i]);
    }
    if (dp[M] == INF) cout << -1;
    else cout << dp[M];
    cout << '\n';
    return 0;
}

Reference

• 백준(2294번) - 동전 2