2293번 동전 1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 $2^{31}$보다 작다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, money;
vector<int> vi;
int mp[10001] = { 0, };

void solve()
{
	cin >> N >> money;
	int num;
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		vi.push_back(num);
	}
	mp[0] = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = vi[i]; j <= money; j++)
		{
			mp[j] += mp[j - vi[i]];
		}
	}
	cout << mp[money];
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}

풀이

동전 어렵다. 반복해서 푸는 방법을 선택했다. 이전에 1,2,3을 이용해서 수를 만드는 것과 비슷한 맥락이었지만, '순서만 다른 것은 같은 경우이다' 라는 조건으로 달라졌다.

우선 1로 N을 만드는 경우의 수는 모두 1이다. 1로 모든 수를 만들 수 있기 때문.
2로 N을 만드는 경우의 수를 생각해보자.
일단, 2는 1을 절대 만들 수 없다.
2를 이용해서 2를 만드는 경우 1번
2를 이용해서 3을 만드는 경우 1과 2를 사용하면 된다.
2를 이용해서 4를 만드는 경우 1을 이용하여 2를 만든 경우에 2를 추가 && 2를 이용하여 2를 만든 경우에 2를 추가 (1+1+2 && 2+2)
한마디로 (1을 이용하여 2를 만든 경우의 수들에 2를 더한 것이 4를 만드는 경우의 수가 됨)
1로만 4를 만드는 경우에 위 경우를 더하면 4를 만드는 경우의 수가 된다.

위의 방식대로 생각한다면
1, 2, 5를 이용하여 만든다고 할 때

1. 1을 이용하여 첫 세팅을한다.
2. 2를 이용하여 만들 때 dp += dp[i-2] 형식으로 쌓아 올린다.
3. 동일한 형식으로 사용하는 코인들을 모두 적용한다.

연관 : DP