[👊DP뿌시기 #13] (BOJ 2293) 동전 1

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

2293번: 동전 1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

---

접근법

DP[i] = i원이 되는 가짓수

 

3 10
1
2
5

예를 들어, 위 예시를 토대로 하나하나 접근해보자.

 

DP[3]은 어떻게 구할까?

1. DP[2] + 1원 

2. DP[1] + 2원

두 가지 방법존재한다.

 

for문을 돌면서(j) 각 동전을 이용해서 i원이 되도록 하여 점화식을 도출했다.

DP[i] += DP[i - arr[j]]

( arr: 동전 배열)

 

그러나 문제에서 짚고 넘어가야 하는 점은 순서는 고려하지 않는다는 것이다.

 

그러면 금액 i를 기준으로 동전j를 돌리면 중복되는 것들이 나오게된다.

따라서, 동전 j를 기준으로 금액 i가 되는 가짓수를 계산하면 된다.

// (X)
for (int i = v[0]; i <= k; i++) {
    for (int j = 0; j < n; j++) {
        dp[i] += dp[i - v[j]];
    }
}

// (O)
for (int j = 0; j < n; j++) {
    for (int i = v[j]; i <= k; i++) {
        dp[i] += dp[i - v[j]];
    }
}

동전을 기준으로 하면 동전을 오름차순으로 정렬할 필요가 없다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 10001

using namespace std;

vector<int> v;
int dp[MAX];

int n, k;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	dp[0] = 1;
	for (int j = 0; j < n; j++) {
		for (int i = v[j]; i <= k; i++) {

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

		}
	}
	cout << dp[k];
}