이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 75 번째 글 입니다.
목차
실버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
- 2로써 만들 수 있는 것을 업데이트 한다.
- 5로써 만들 수 있는 것을 업데이트 한다.
- 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;
}