[백준] 2293 동전 1 (복습 + 최적화)

문제

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

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

입력

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

출력

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

 

 

7달 전 맞았던 코드입니다.

#include<bits/stdc++.h>
using namespace std;

int arr[2][10001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<int>num;
    int n, k, x;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> x;
        num.push_back(x);
    }
    sort(num.begin(), num.end());
    arr[0][0] = 1; arr[1][0] = 1;
    for (int i = 1; i <= k; i++) {
        if (i % num[0] == 0) {
            arr[0][i] = 1;
        }
        else
            arr[0][i] = 0;
    }
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = 0; l <= j / num[i]; l++) {
                  sum += arr[0][j - num[i] * l];
            }
            arr[1][j] = sum;
            sum = 0;
        }
        for (int j = 1; j <= k; j++) {
            arr[0][j] = arr[1][j];
        }
    }
    cout << arr[0][k];
}

i번째 동전까지 사용할 수 있을때, j원을 만들때

    i번째 동전을 0개,1개,,,,,,n개 사용하고 i-1번째 동전까지 사용할 수 있는 값을 모두 더했습니다.

복잡하고, 코드도 너무 길었습니다.

심지어 메모리까지 초과해서 dp2차원배열을 n*k에서 2*k로 줄여 간신히 통과했습니다.

 

새로운 코드입니다. 너무너무 간단합니다......................................

#include<iostream>
using namespace std;
int dp[10001];
int main() {
	dp[0] = 1; //x원의 동전을 사용했을때, 채워야할 나머지금액이 없는경우의 수는 1입니다.
	int n, k, x;
	cin >> n >> k;
	while (n--) {
		cin >> x;
		for (int i = x; i <= k; i++) {
			dp[i] += dp[i - x]  
            //while문을 한번 돌 때마다, 사용할 수 있는 동전의 종류는 하나 늘어납니다. (입력됨)
            //dp[i]는 i원을 만들기 위한 경우의 수 입니다.
            //매번 while문에서, dp[i]+=dp[i-x]를 수행합니다.
            //dp[i-x]는 동전x를 하나 사용했을때, 나머지 i-x원을 만드는 경우의 수 입니다.
            //dp[i-x]도 동전 x를 하나 사용했을 때 경우의 수를 포함하므로, 결국 배열dp는 동전 x를 몇개든 사용한 데이터를 포함합니다.
		}
	}
	cout << dp[k];
}

각 while문 마다, 동전x를 사용합니다. dp[x]부터 dp[k]까지만 갱신할 수 있으므로 for문은 i=x부터 x<=k까지 돕니다.

dp[i]는 동전x를 사용해 i원을 만들 수 있는 경우의 수인데, 기존 dp[i]값에 dp[i-x]를 더하면 동전 x를 하나 사용했을 때, 나머지 금액을 채우는 경우의 수를 더하게 됩니다.

 i는 x부터 k까지이므로,,,, 

   i가 2*x 또는 n*x 보다 커지게 되는 경우 dp[i-x]는 이미 갱신된 값입니다. 따라서, 동전x를 하나만 더 사용했을때의 경우의 수만 더해주어도 dp[k]는 모든 경우의 수를 더하게 됩니다.