백준 Gold 4 동전 1

동전 1 (백준 Gold 4)

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

DP 문제이다
N개의 가치가 서로 다른 동전이 주어지고
그를 통해 K원을 만드는 문제이다

동전은 얼마든지 사용해도 되나
사용한 동전의 구성이 같은 경우는 1개로 친다
(ex : 5원을 만드는데 1 1 2 1 과 1 2 1 1 은 같은 것으로 침)

점화식?

일단 내가 세운 식은 이렇다

dp[k] : k까지 주어지는 동전의 경우의 수
라 하면
dp[k] = dp[k - c1] + dp[k - c2] …

k값에서 각각의 동전의 값을 뺀 dp 값들을 더해주면
k의 경우의 수를 구할 수 있을 것이라 판단하였다

처음 제출한 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> coins(n);
	vector<int> dp(k + 1, 0);
	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;

		if (t <= k)
		{
			coins[i] = t;
		}
	}

	sort(coins.begin(), coins.end());

	for (int i = 0; i < k; i++)
	{
		// 현재 이 수를 표현할 방법이 없음
		if (dp[i] == 0)
			continue;

		for (int c : coins)
		{
			if (i + c <= k)
			{
				dp[i + c] = dp[i] + 1;
			}
		}
	}

	cout << dp[k];

	return 0;
}

틀리고 나서 다시 한번 보니
= 로 ‘덮어쓰기’를 하고 있으며
일반적인 조합/순열 카운팅 이라면 += 를 해주어야 했다

+= 로 바꿔보니 수치가 지나치게 높아졌고
해당 로직이 틀림을 알 수 있었다

왜 틀렸는가?

해당 반복문 코드는
0~k 까지 돌면서
i + Coin의 값어치 만큼 돌고 있다

+= 로 바꿨을때 값이 치솟는 것을 보고
‘코드’가 ‘중복된 조합’을 고려하지 않고
‘모든 순서’를 고려하는 ‘순열’을 구하는 방식에 가까웠다

따라서 각각의 Coin들이
개별적으로 k까지 진행하는 것이
‘중복’된 요소를 없애는 방식이라 생각하였다

최종 제출 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> coins;
	vector<int> dp(k + 1, 0);
	for (int i = 0; i < n; i++)
	{
        int t;
        cin >> t;
		if(t <= k)
        {
            coins.push_back(t);
        }
	}
    
    n = coins.size();
    
	// 0을 만들게 되는 경우 + 1
	dp[0] = 1;

	// 반복문을 도는 주체가 coin 일것
	// 각 '수'마다 돌 경우 (0~k) - 코인들의 결과가 섞임
	for (int c : coins)
	{
		for (int i = c; i <= k; i++)
		{
			dp[i] += dp[i - c];
		}
	}

	cout << dp[k];

	return 0;
}

해설

dp[0] = 1로 두어
dp[i - c] 부분에서 ‘값이 맞아 떨어지는 경우’의
초기값을 세팅하였다
(ex : 5원으로 5를 표현하는 방법은 1이므로)

이후 각각의 Coin을 기준으로 반복문을 돌며
코인의 값 c 부터 k 까지 진행

dp[i] += dp[i - c]를 통해 값을 더해준다

• 순서는 중요치 않다
  각각의 코인들의 결과가 += 로 더해지며
  다음 코인 역시 그 결과값을 사용
  

• 개인적으로는 입력 코인값이 k를 넘어간 경우
  포함시키지 않은 후, n 값을 coins로 재 지정하였다
  

결과

이번에는 점화식을 잘 세운듯 하였으나
알고보니 ‘조합’에 관한 내용이 아니라
다른 점화식을 세우는 삽질을 했었다

아직 dp에 대한 갈길이 먼듯하다