[BOJ / C++] 2293번 : 동전 1

문제

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

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

입력

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

출력

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

Solved.ac 레벨

골드 V

풀이

오늘도 열심히 다이나믹 프로그래밍.

여전히 내 두뇌는 다이나믹하게 돌아가는 것을 거부하고 있다.

단순히 경우의 수를 다 구해보면 식이 보이겠지 하고 1원을 만드는 경우부터 10원을 만드는 경우까지 일일이 손으로 다 적어보았는데, 역시나 규칙을 찾을 수가 없었다. 그도 그럴게 이 문제는 주어지는 n개의 동전의 가치가 다르기 때문이다. 다른 분들의 풀이를 보고서야 1원으로 1 ~ 10원을 만드는 경우, 2원으로 1 ~ 10원을 만드는 경우... 이런 식으로 구해나간다는 것을 깨달을 수 있었다.

 

그렇게 깨달은 것을 토대로 예제를 설명해보자.

예제는 n = 3, k = 10, coin = { 1, 2, 5}인 경우이다.

 

coin

index	0	1	2
value	1	2	5

동전의 가치는 위와 같은 배열로 저장하여 사용할 것이다. 이제 각각 동전의 가치를 가지고 1원부터 10원을 만드는 경우를 살펴보자.

dp[] 배열을 사용할 것이며, dp[x] = y; 로 나타내어 x원을 만드는 경우의 수는 y가지라는 것을 표시할 것이다.

먼저 dp[0] = 1으로 초기화한다. 0원을 만드는 경우의 수는 동전을 한 번도 사용하지 않는 한 가지 경우 뿐이다. 이 초기식이 상당히 중요한 역할을 한다.

 

* 표에서 첫 번째 행은 n원을, 두 번째 행은  dp[n]을 나타낸다.

1원을 사용할 때

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

1 ~ 10원을 만들 때 1원 동전을 사용하는 경우의 수는 1, 1 + 1, ... , 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 각 1가지 씩이다.

1 ~ 10원을 i 이라고 했을 때 dp[1]의 경우,

dp[1] = dp[1] + dp[0] 으로 나타낼 수 있다. dp[0]은 1로 초기화 되어있고, 나머지 dp 배열은 0으로 초기화되어있기 때문이다.

 

2원을 사용할 때

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

1원을 만들 때에는 2원을 사용할 수 없다. 따라서 2원을 사용할 수 있는 2원을 만드는 경우부터 2를 사용해나간다. 2원을 사용할 수 있는 경우는 위처럼 확인할 수 있다. 예를 들어 4원을 만드는 경우, 현재 4원을 1원으로 만드는 경우 + 2원을 만드는 경우이다.

? 2원을 만드는 경우 : (1 + 1), 2  -> 2가지

? 1원, 2원을 사용해 4원을 만드는 경우 : (1 + 1 + 1 + 1), (1 + 1 + 2), (2 + 2) -> 3가지

 

5원을 사용할 때

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	5	6	7	8	10

1 ~ 4원을 만들 때에는 5원을 사용할 수 없다. 따라서 위와 마찬가지로 5원을 사용할 수 있는 최소의 경우인 5원을 만드는 경우부터 5원을 사용해나간다. 

 

위의 과정에서 확인할 수 있는 것은

1. 동전의 종류만큼 반복을 돌며
2. 현재 만들어야 하는 금액이 n이라면 dp[n] = dp[n] + dp[n - 동전의 종류]와 같다.
ex)동전이 2원이고 구해야 하는 금액이 4원이라면 dp[4] = dp[4] + dp[4 - 2]

 

즉 점화식은 아래와 같다.

int n = 3;
int coin[] = {1, 2, 5};
int k = 10;

for(int i = 0; i < n; i++) {
	//coin 배열을 순회한다. 1~2 => 1, 2, 5
	for(int j = coin[i]; j <= k; j++) {
    	//해당 코인을 이용할 수 있는 최소의 경우부터 k원을 만드는 경우까지 반복한다
        //1 ~ 10, 2 ~ 10, 5 ~ 10
        dp[j] += dp[j - coin[i]];
     }
}

Code

#include<bits/stdc++.h>

using namespace std;

int n, k;
vector<int> coin;
int dp[10001];

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

    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        coin.push_back(input);
    }

    dp[0] = 1; //0원을 만드는 방법은 아무 동전도 사용하지 않는 방법 1가지

    for(int i = 0; i < coin.size(); i++) {
        for(int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }

    cout << dp[k] << "\n";

    return 0;
}

반복숙달 반복숙달 반복숙달 DP...

 

2293번: 동전 1