[백준] 알고리즘 2293번 - 동전 1 문제

문제

www.acmicpc.net/problem/2293

2293번: 동전 1

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[10001];
int arr[101];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> arr[i];
	dp[0]=1;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			if (arr[i] <= j) {
 				dp[j] = dp[j] + dp[j - arr[i]];
			}
		}
	}
	cout << dp[k];
}

풀이

1. 0을 만드는 경우 -> 처음에 그냥 아무것도 선택하지 않은 경우 즉 dp[0]=1 초기값을 설정해줌.

2. dp[j] -> 코인의 종류는 j 코인이 최소 포함되어 만들 수 있는 경우의 수

1원짜리 코인으로 k번째 즉 10원까지 만들 수 있는 경우의 수는 1원을 포함해서 10원을 만들어야하닌간 한가지의 경우의 수밖에 없다

그다음 2원짜리 코인으로 2원을 최소 한개이상 포함해서 10원까지 만들 수 있는 경우의 수는 0  1 은 2원이 포함되지 않으니 0으로 설정되어야 한다. 그 이후 2원부터는 저위의 그림처럼 가져온다는 것을 알 수 있다.

 

즉 2차원 배열로 만들 수 있는데 2차원 배열로 만들게되면 메모리 초과가 나게된다.

그래서 1차원 배열로 점화식을 세울 수 있는데

dp[j] = dp[j] + dp[j - arr[i]];

이 문제와 비슷한게 평범한 배낭 문제가 있다.

www.acmicpc.net/problem/12865

12865번: 평범한 배낭