C++ / 2293 / 동전 1 ( 다이나믹 프로그래밍 )

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

문제 요약

n가지 종류의 동전이 있습니다. 각각의 동전이 나타내는 가치는 다릅니다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶습니다. 그 경우의 수를 구해야합니다.

문제 풀이

1. 동전의 갯수와 경우의 수를 얻고 싶은 숫자를 입력받습니다.

2. 동전의 갯수만큼 동전의 값어치를 벡터 배열로 입력받습니다.

3. dp함수를 만들어 동전의 갯수 만큼 반복하고 그 안에서는 원하는 숫자만큼의 경우의수를 계산하는 bottom-up 로직을 구현합니다.

4. 동전의 갯수 만큼 반복하는 이유는 경우의 수 배열을 동전의 값어치 별로 중첩하기 위해서 입니다.

ex ) 동전이 1원, 2원, 5원짜리가 있을때 1부터 10까지의 동전별 경우의 수 합입니다.

	1	2	3	4	5	6	7	8	9	10
1원	1	1	1	1	1	1	1	1	1	1
2원	1	2	2	3	3	4	4	5	5	6
3원	1	2	2	3	4	5	6	7	8	10

 5. 여기서 경우의 수를 구하는 로직은 현재 숫자 = 동전의 값어치 면 무조건 1번만 ( 그 동전 기준 ) 경우의 수가 생기기 때문에 1을 더해주었고 그 외에는 현재 숫자 - 동전의 값어치 ( 현재 숫자에서 동전의 값어치 만큼 빼면 이미 구했던 경우의 수 EX) 7( 현재 숫자 ) - 5( 동전 값어치 ) = 2  (2는 이미 2원에서 경우의수 2가  나왔었음 ))를 더해주었습니다.

6. 경우의 수가 담긴 배열에 얻고 싶은 숫자를 인덱스에 넣고 출력하면 됩니다.

주의할 점

이번 문제는 푸는데 시간이 좀 많이 걸렸던 것 같습니다.

일단 bottom-up 기반으로 풀려 하였지만 값이 증가하는 형태가 무턱대고 이전 항과의 합으로는 만들기가 어려웠습니다.

현재 숫자에서 동전의 값어치를 빼면  전에 구했던 경우의 수 라는것을 눈치채는  것이 중요합니다.

코드 

#include<iostream>
#include<vector>

using namespace std;

int n, k;
vector<int>v;
int p[10004];
void dp()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = v[i]; j <= k; j++)
		{
			if (j == v[i])
			{
				p[j] += 1;
			}
			else
			{
				
				p[j] += p[j - v[i]];
			}

		}
	}
}
int main()
{
	cin >> n >> k;
	if (n <= 0 || n>100)
	{
		return 0;
	}
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		if (a > 100000)
		{
			return 0;
		}
		v.push_back(a);
	}	




	dp();



	cout << p[k];

	return 0;
}

반응형

예제

3 10
1
2
5

결과