[백준/C++] 2293번 : 동전 1 (DP 문제, 경우의 수)

동전 1 

문제

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

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

입력

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

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

예제 입력 1

3 10
1
2
5

예제 출력 1

10

---

해당 문제는 DP를 이용하여 경우의 수를 구하는 문제이다.

지금까지 경우의 수를 구하는 문제는 BFS로만 풀어봤는데, DP로 푸는건 처음이라 감 잡기가 어려웠다.

 

문제는 간단하다. k로 입력받는 금액을 동전 n들로 만들 수 있는 경우의 수를 구하는 것이다.

 

처음엔 2차원 배열을 이용해서 풀어보려했지만, 정답이 도출되지 않았다.

 

예제로 나온 1,2,5 동전을 이용해서 10을 만드는 경우의 수에 대해 설명해보겠다.

 

 

1을 이용해서 1원을 만들 수 있는 경우의 수는 1개, 1을 이용해서 5를 만들 수 있는 경우의 수도 1개(1+1+1+1+1), 10을 만들 수 있는 경우의 수도 1개이다. (1+1+1...10번..+1)

 

 

이제, 1원과 2원을 이용해서 1원부터 10원까지를 만들 수 있는 경우의 수를 계산해보았다.

2원을 통해 1원을 만들 순 없으므로 0가지, 2원은 2원 하나로 만드므로 1가지가 나온다.

 

1원과 2원을 통해 3원을 만들 수 있는 경우의 수는 1가지인데, 이는 3 - 2 = 1원이 만들어지는 경우의 수를 보면 된다.

1원의 경우의 수를 봐야하는 이유는, 1원과 2원을 이용하여 3원을 만든다고 할 때, 2원을 이미 이용했다고 보면, 1원과 2원을 이용해서 1원만 만들면 된다. 그럼 이미 사용한 2원과 1원이 더해져 3원을 만들 수 있는 것이다.

 

즉, 3원은 2원을 뺀 1원의 경우의 수 (1원 경우의 수 + 2원 경우의 수)를 다 더한 결과가 3원을 만들 수 있는 경우의 수와 같다는 것이다.

따라서 3원은 1원의 경우의 수 1 과 2원의 경우의 수 0을 더해 1이 된다.

(미리 사용했다고 한 2원짜리 동전 하나와, 1원짜리 동전 하나를 사용해서 3원이 만들어 진 것)

 

다음 예시도 자세히 보자.

 

1원과 2원을 이용하여 6원을 만들 수 있는 경우의 수는 3가지이다.

6원에서 2원을 뺀 4원의 경우에 수에서 2원을 그대로 얹기만 하면 되는거니까, 4원의 경우의 수 (1원의 경우의 수 1 + 2원의 경우의 수 2)를 각각 더해 3가지가 나온다.

 

이와 같은 동일한 방법으로 10원까지의 경우의 수를 모두 구해주고, 1원의 경우와 수와 2원의 경우의 수를 구한 토탈 경우의 수는 10원에서 6가지가 나온다.

 

자, 이제 5원을 추가하여 1원부터 10원까지 만들 수 있는 경우의 수를 구해보도록 하자.

 

 

5원도 마찬가지로, 구하고자 하는 금액 - 5원의 경우의 수를 따지면 된다. 

우선 4원까지는 5원으로 절대 만들 수 없기 때문에 0가지 경우를 가지고, 5원은 5원 1개로 만들 수 있으므로 1가지 경우를 갖는다.

6원은 5원 하나와 1원을 통해 만들 수 있다. 따라서 5원은 이미 포함되어있다고 보고, 1원의 경우의 수 1이 6원의 경우의 수와 같으므로 1가지가 나온다.

 

동일하게 10원까지 경우의 수를 다 구하고, 1,2,5원의 모든 경우의 수를 더하여 총합을 나타내면 10원의 총 경우의 수는 10가지가 나온다는 것을 알 수 있다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;
	vector<int> coin(n);
	for (int& c : coin)
		cin >> c;

	vector<int> dp(k + 1);
	dp[0] = 1;
	for(int i = 0; i < n; i++)
	{
		for (int j = coin[i]; j <= k; j++)
			dp[j] += dp[j - coin[i]];
	}
	cout << dp[k];

	return 0;
}

 

소스코드를 이용하여 위의 개념을 작성한 결과이다.

dp[0] 은 아무것도 선택하지 않은 경우의 수 1가지를 나타내었다.

dp[j]는 dp[j - coin[i]]; 를 구하여 동전값 coin[i]를 이미 사용했다고 가정하고 뺀 dp[j]값을 더해주었다.

---

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

2293번: 동전 1

https://www.youtube.com/watch?v=2IkdAk1Loek : 참고하면 좋을 설명영상