<Baekjoon> #2293 Dynamic Programming_동전1 c++

#2293 동전1
참고

💡Summary & Idea

• n가지 종류의 동전을 사용하여 k원을 만드는 경우의 수를 구하는 문제 (순서만 다른 경우는 같은 경우이다)

dp[a]=b일 때, a원을 만드는 방법은 b개이다 라고 정했을 때
우선 dp[0]=1이다. 0원을 만드는 방법은 하나도 선택하지 않는 경우로, 이 경우를 1가지로 친다

예를 들어 3원을 만든다고 할 때
{1+2} 는 1원을 만드는 방법에서 2원을 더하는 경우다
이 말은 dp[3]+=dp[3-2]=dp[1]
{0+3} 는 0원을 만드는 방법에서 3원을 더하는 경우다
이 말은 dp[3]+=dp[3-3]=dp[0]

현재 동전이 X원이고, Y원을 만들고 싶다면
dp[Y]=dp[Y]+dp[Y-X] (Y>=X)

🖊️Solution

✔️ 예제에서 동전이 {1,2,5}원이 있을 때
첫 번째 동전 1원만을 사용해서 Y원을 만드는 경우는
dp[Y]+dp[Y-1]

1원만 사용한 상태에서 두 번째 동전 2원을 추가로 사용하여 Y원을 만드는 경우를 더해준다 (Y>=2)
dp[Y]+dp[Y-2]

1원, 2원을 사용한 상태에서 마지막 동전 5원을 추가로 사용하여 Y원을 만드는 경우를 더해준다 (Y>=5)
dp[Y]+dp[Y-5]

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int N, K;

int main() {
	cin >> N >> K;
	vector<int> coin(N);
	vector<int> dp(K + 1);

	dp[0] = 1;

	for (int i = 0; i < N; i++)
		cin >> coin[i];
	for (int i = 0; i < N; i++) {
		for (int j = coin[i]; j <= K; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}
	cout << dp[K] << endl;
	return 0;
}