🖊️ 문제

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

---

🖊️ 풀이

그리디..라고 생각했다.
완전탐색?
흠..

근데 아무리 생각해도 떠오르지 않았고...

내 능력으로는 풀기 어려운 문제라고 느껴져서
구글신의 힘을 좀 빌렸다.

근데 이건 완전 배낭문제였다.

---

문제를 요약해보면,
"N개의 동전들로 M원을 만드는 경우의 수를 찾아라"

동전 i개를 이용해서 M원을 만드는 경우의 수를 찾아가며, 동전을 하나씩 추가해가야 한다.

M원을 만들 수 있는 경우의 수는,
1원부터 시작해서 올라간다.

1원, 50원, 100원으로 1000원을 만들자.

dp[0] = 1
0원을 만드는 경우의 수는 1개

1원으로 만들기

dp[1] = 1
dp[2] = 1
dp[3] = 1
..
dp[1000] = 1

50원으로 만들기

dp[50] = 2
: 1원으로 만든 dp[50] + 50원*1 1개 추가
dp[51] = 3
: 1원으로 만든 dp[51] + dp[50]
(50원 만들고 1원짜리로 만들면 됨)
dp[52] = dp[52] + dp[51]
...
dp[100] = dp[100] + dp[99]
dp[1000] = dp[1000] + dp[999]

100원으로 만들기

dp[100] = dp[100] + dp[0]
dp[101] = dp[101] + dp[100]
...
dp[1000] = dp[1000] + dp[999]

바텀업방식으로 하나씩 쌓아올리면 된다.
그래서 점화식은

for (int i = 0; i < n ; i++) {
	for (int j = cost[i] ; j <= m ; j++) {
    	dp[j] += dp[j - cost[i]];
    }
}

배낭..넘어려워

#include <iostream>
#include <memory.h>
using namespace std;

int coins[21];
int dp[10001];

int main()
{
	int t;
	cin >> t;

	int n, m;
	int result = 0;
	for (int tk = 0; tk < t; tk++) {
		result = 0;
		memset(coins, 0, sizeof(coins));
		memset(dp, 0, sizeof(dp));

		cin >> n;
		
		for (int i = 0; i < n; i++)
			cin >> coins[i];
		cin >> m;

		dp[0] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = coins[i]; j <= m; j++) {
				dp[j] += dp[j - coins[i]];
			}
		}
		cout << dp[m] << endl;
	}
}

참고
https://kth990303.tistory.com/207
https://kth990303.tistory.com/216