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