[백준/C++] 동전 1

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 k의 크기가 10000으로 제한되어 있기 때문에 쉽게 풀 수 있는 문제다.

 

동전의 가치가 전부 다르고 몇 개를 사용해도 되며, k원을 만드는 모든 경우의 수를 구해야 된다.

 

for문으로 j원의 돈을 만들 수 있으면 j원에 coin을 더해 [j+coin]원을 만들 수 있다.

 

이때, coin을 여러개 사용할 수 있으므로 [j+coin*2], [j+coin*3] ... 도 만들 수 있다.

coin에 숫자를 곱해 더하는 방법도 있겠지만, 좀 더 편한 방법이 있다.

 

예를 들어 2, 4의 동전이 주어지고 k가 10이라고 하자

그러면 2로 만들 수 있는 돈의 가치에 대한 경우의 수는 아래 그림과 같다.

 

그러면 2로 만들 수 있는 돈의 가치에 대한 경우의 수는 아래 그림과 같다.

 

이제 4의 동전도 사용해서 만들 수 있는 돈의 가치는 어떻게 될까?

for문으로 value[i+coin]+=value[i]와 같은 형식으로 나타낼 수 있다.

 

먼저 4원동전 하나만 사용하면 4원의 가치를 갖는 동전을 만들 수 있다.

그러면 4원을 만드는 경우의 수는 2개가 된다.

 

이제 8원을 만드는 경우의 수는 어떻게 될까?

4원을 만드는 경우에 4원을 더하면 된다.

 

즉, 이전에 4원을 한 개 사용하는 경우가 4에 들어가 있으므로 이 경우에 4원을 더하는 경우는 4원을 2개 쓰는 경우가 포함되게 된다.

(4원을 2개 사용하는 경우를 따로 구하지 않아도 된다는 뜻)

 

그러므로 4원을 1개 쓰는 경우, 4원을 2개 쓰는 경우로 구분하지 않고 단순히 for문으로 탐색해 경우를 더하는 것 만으로도 4원을 여러개 쓰는 경우가 포함되게 된다.

 

요약하자면 현재 동전이 coin원이라면 for문으로 [i+coin]원을 만드는 경우의 수에 [i]원을 만드는 경우의 수를 더하는 것으로 문제를 풀 수 있다.

 

​

[아이디어 정리]

1. i원을 만드는 경우의 수를 저장할 vector를 만든다.
2. for문으로 0 ~ k-coin원까지 탐색을 돌려 [i]원을 만드는 경우의 수를 [i+coin]원을 만드는 경우의 수에 더한다.
3. 모든 동전으로 경우의 수를 구했으면 k원을 만드는 경우의 수를 출한다.  

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int n, k;
	cin >> n>>k;
	vector<int> value(k + 1, 0);
	value[0] = 1;
	int coin;
	for (int i = 0; i < n; i++) 
	{
		cin >> coin;
		for (int j = 0; j<= k; j++) 
		{
			if (j + coin <= k)
			{
				value[j + coin] += value[j];
			}
			else break;
		}
	}
	cout << value[k];
	return 0;
}

 

---

DP는 처음 풀 때 정말 어렵다고 느꼈는데, 많이 풀면서 익숙해지면 생각보다 쉽게 해결할 수 있는 문제들도 많은 것 같다.

EZ

 

2293번: 동전 1