[BOJ / C++] 2294번 : 동전 2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

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

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

Solved.ac 레벨

골드 V

풀이

최근에 풀었던 2293번 : 동전 1과 유사한듯 유사하지 않았던 문제였다. 보통 시리즈 문제들은 풀이가 거기서 거기던데...

2293번 : 동전 1 풀이 보기

아무튼 이 문제는 원하는 액수를 주어진 종류의 동전으로 구성하며 동전의 개수를 최소로 하는 문제다.

 

먼저, 최소값을 구해야 하므로 dp배열의 요소는 dp[0]을 제외하고 0이 아닌 k의 최대값인 10000을 넘긴 값, 10001 (이하 INF) 로 초기화를 해주었다. 이제 이 값과 비교해나가며 값을 대체해나갈 것이다.

 

예제를 통해 내가 생각한 바를 설명해보도록 하겠다.

n = 3, k = 15, coin = { 1, 5, 12 }

 

dp 배열 초기값

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF

1원 동전을 사용할 때

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

1원을 사용할 때에는 1원 동전을 인덱스만큼 사용해야 한다. 이 값들은 INF와 비교하여 모두 작은 값이기 때문에 dp 배열의 값을 대체하게 된다.

ex) dp[1] = min(INF vs 1) = 1

 

5원 동전을 사용할 때

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	1	2	3	4	5	2	3	4	5	6	3

5원을 사용할 수 있는 경우는 5원을 만들 때부터 사용이 가능하다.

5원 1개를 사용하는 경우의 수는 dp[0] + 1과 같다. 아무것도 사용하지 않은 상태에서 5원짜리 1개를 사용하는 경우이기 때문이다.

또 예를 들어 7원을 만드는 경우에는 2원을 만드는 최소 경우의 수에 5원 1개를 더하는 것과 같다.

또, 12원을 만드는 경우에는 7원을 만드는 최소 경우의 수에 5원 1개를 더하는 것과 같다.

이를 배열로 나타내면 dp[i - 5] + 1이다.

이렇게 구한 경우의 수를 기존에 저장되어 있던 값과 비교하여 최소값을 넣어야 한다.

ex) dp[5] = min(5 vs 1) = 1

 

12원 동전을 사용할 때

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

역시 12원을 사용할 수 있는 경우는 12원을 만들 때부터 사용이 가능하다.

5원을 사용할 때와 마찬가지로 인덱스에서 12를 뺀 뒤 1개를 더한다.

즉 12원을 만드는 경우에는 아무 동전도 없는 상태에 12원 동전 1개를 더하는 것이고, 13원을 만드는 경우에는 1원을 만드는 경우 + 12원 동전 1개를 더하는 것이다.

15원의 경우 값이 변화되지 않았는데, 이는 5원 동전을 활용하는 경우의 수가 12원을 활용하는 경우의 수보다 동전을 적게 사용하기 때문이다.

 

위를 통해 알아본 규칙은 다음과 같다.

n원을 만드는 경우의 수를 구할 때

dp[n] = min(dp[n], dp[n - 동전의 금액] + 1);

 

따라서 다음과 같은 점화식을 얻을 수 있다.

//coin = {1, 5, 12};
//k = 15;

for(int i = 0; i < coin.size(); i++) {
	for(int j = coin[i]; j <= k; j++) {
    	//ex)5원을 사용하려면 5원을 만드는 경우부터 가능
        //따라서 i번째 코인의 값부터 시작하여 값을 대체
        dp[j] = min(dp[j], dp[j - coin[i]] + 1);
    }
}

Code

#include<bits/stdc++.h>
#define INF 10001

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] = 0; //0원을 만드는 방법은 아무 동전도 사용하지 않는 방법 1가지

    for(int i = 1; i <= k; i++) {
        dp[i] = INF;
    }

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

    if(dp[k] == INF) {
        cout << -1 << "\n";
    } else {
        cout << dp[k] << "\n";
    }



    return 0;
}

시리즈 문제라 날먹할 수 있을 줄 알았는데 크윽...

 

2294번: 동전 2