[알고리즘] C++ 백준 2293 동전1

백준 2293

https://www.acmicpc.net/problem/2293

2293번: 동전 1

풀이 전 나의 생각

n개의 동전을 조합하여 k원이 되게하는 문제다.

 

우선 먼저 생각할 수 있는건 n번째의 동전을 탐색하면서 얻을 수 있는 조합을 찾아내야 한다는 것이다.

그럼 1원이 3원(k = 3)까지 증가하면서 DP값을 구한다고 가정해보자.

 

DP[1] - 1원이 될 수 있는 방법은 '1' 한 가지

DP[2] - 2원이 될 수 있는 방법은 '1 + 1' 한 가지

DP[3] - 3원이 될 수 있는 방법은 '1 + 1 + 1' 한 가지

 

다음으로 2원이 3원이 될 수 있는 방법은

'1 + 2' 한 가지다.

그럼 1원을 만들 수 있는 방법은 이전에 만들어 놨으니 DP[1]을 참조하면되고

2를 만들 수 있는 방법 DP[2]를 더해서 DP[2]에 갱신해주면 될것이다.

 

더 자세히 설명하자면 1, 2, 3 원으로 10원을 만든다고 가정하면

위에 과정을 통해 차근차근 DP[n] 즉, n원이 될 수 있는 방법을 쌓아 올릴 것이다. (여기서 n은 위와 관련 없음)

다음으로 3원으로 1부터 10까지 만드는 과정을 진행할 때 5원을 만들어야 하는 과정이라고 가정하자

3 + n을 해야하는데 n은 2일 것이다. 그럼 DP의 최적값을 구하기 위해선 2를 만들 수 있는 모든 과정을 더해야 하니 

목표값 5원 - 현재 동전 가치값 3원 을 해야 한다. 그리고 5원이 될 수 있는 모든 과정 값을 갱신 해주면 현재 만들 수 있는 과정의 최적값을 얻을 수 있다.

 

이를 점화식으로 나타내면 DP[v] = DP[v] + DP[v - a]  (v = 만들고 싶은 금액, a = 현재 가치)

 

결론은 이전에 구할 수 있는 모든 과정값을 참조하면서 현재 구할 수 있는 과정의 최적값을 갱신해 나가야한다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

int dp[10001];
int val[101];

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k = 0;

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> val[i];
	}

	dp[0] = 1;

	for (int i = 0; i < n; i++)
	{
		for (int j = val[i]; j <= k; j++)
		{
			dp[j] = dp[j] + dp[j - val[i]];
		}
	}

	cout << dp[k];
}