[백준] 2293 동전1 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI

2293 동전1

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

 

동전 0 문제는 그리디 알고리즘을 활용했다면

동전 1 문제는 DP(Dinamic Algorithm, 다이나믹 알고리즘)을 사용한다.

 

---

예제에서 동전은 총 3 종류, 1 2 5 가 있다.

arr 배열로 동전의 가치들을 저장해주고

문제는 dp 배열을 사용하여 접근한다.

 

먼저 dp [0]=1로 두는데, 이는 아무 동전도 선택하지 않은 경우도 하나의 경우의 수인 것이다.

각각의 동전에 대하여 for문을 돌린다.

 

 

먼저 동전 1에 대해서 10원을 만드는 경우의 수를 계산해준다.

1(=j)부터 10(=k)까지 dp[j] += dp[j - 1] 을 해준다.

동전 2에 대해서는 0원과 1원은 만들지 못하니 패쓰하고

j = 2부터 10(=k)까지 dp[j] += dp[j - 2] 를 해준다.

마찬가지로 동전 5에 대해서도

j = 5부터 10(=k)까지 dp[j] += dp[j - 5] 를 해준다.

정답은 dp[k] 를 출력해주면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	vector<int> dp(k+1);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = 1;	// 아무 동전도 선택하지 않은 경우
	for (int i = 0; i < n; i++) { //각 동전에 대해
		for (int j = arr[i]; j <= k; j++) { 
			dp[j] +=dp[j - arr[i]];
		}
	}

	cout<<dp[k]<<endl;
	return 0;
}