백준 2293번 _ 동전 1

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

2293번: 동전 1

풀이방법

예시인 1 ,2 5원으로 10원이 나올수있는 동전의 경우의 수를 잘 생각해보자.

 

일단

1원만 사용했을경우

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

 

1, 2원 사용했을 경우

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

 

1, 2, 5원 사용했을 경우

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

 

잘 보면 dp[cost + j] += dp[j] 이 공식이 사용된걸 알 수 있다.

그리고 이 공식은 잘 생각해보면 당연하다. 동작이 어떻게 되는지 보면 이해가 쉬울것이다.

가벼운 예시를 하나 들어 동작을 설명하겠다.

 

 

ex) 1, 2로 5를 만들경우

 

1만 사용해서 각 원들을 만들 경우를 넣어봤다.

1만 사용한 경우

이제 2도 추가해보자.

1, 2를 사용한경우

정답은 3이다. 0원을 만들 경우는 1이다. 이것도 잊지말것.

---

전체코드

#include <iostream>

using namespace std;

int dp[10001];

int main()
{
	int n, k;
	cin >> n >> k;
	int cost;

	dp[0] = 1;
	for (int i = 0; i < n; i++)
	{
		cin >> cost;
		for (int j = 0; j <= k; j++)
		{
			if (cost + j > k)
				break;

			dp[cost + j] += dp[j];
		}
	}
	
	cout << dp[k];
	return 0;
}

---

후기

뭔가 푼 문제도 설명을 하려하니까 어떤 단어로 설명을 해야 될지 어렵다.ㅎㅎ

 

조금 난잡하게 설명한 감이 있지만, 위의 문제는 경우의수를 구하는 것임을 명심한다면 이해가 빠를것이다.