BOJ - 동전 1(2293)

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

생각

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

정의

dp[i] = n의 가치를 만들기 위해 필요한 경우의 수

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

점화식

dp[j] += dp[j-a[i]];

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

3 15
2
5
10

========동전의 값 : 2========
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

========동전의 값 : 5========
1 0 1 0 1 1 1 1 1 1 2 1 2 1 2

========동전의 값 : 10========
1 0 1 0 1 1 1 1 1 1 3 1 3 1 3

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

이 때, 해당 가치가 업데이트 되는 방향은 결정되어 있다. 5의 가치는 3의 가치에서 2의 동전을 더해서 만들 수 있다. 이런 관계를 잘 엮는다면 문제를 해결할 수 있다. 이 문제는 동전 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];
 
void print(int coin){
    cout << "========" << "동전의 값 : "<< coin << "========" << '\n';
    for (int i = 0; i < M; i++) {
        cout << dp[i] << " ";
    }cout << '\n' << '\n';
}
 
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = a[i]; j <= M; j++) {
            dp[j] += dp[j-a[i]];
        }
        print(a[i]);
    }
    cout << dp[M] << '\n';
    return 0;
}
 

Reference

• 백준(2293번) - 동전 2