[백준 BOJ] 2294 동전 2 c++

[백준 BOJ] 2294 동전 2 c++

문제 링크 : 백준 2294 동전 2

2294번: 동전 2

 

문제

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

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

 

입력

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

출력

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

예제 입력 1

3 15
1
5
12

예제 출력 1

3

 

 

---

풀이과정

며칠전 도전했던 코딩 테스트에서 똑같이 나온 유형이다. DP 공부 안했다가 이거 푸는데 오라지게 오래걸렸어서 다시 복습할겸 풀게 되었다. 이전에 풀었던 것보다 뭔가 더 조잡해진 느낌은 있지만, 그래도 푸는 시간은 단축 된 것 같다. 아무래도 여기 의 내용을 계속해서 숙지하고 있어서 그런가보다. 항상 뇌에 큰 문제를 작은 문제로 나눠서 푼다 를 박아두자.

 

1. 메모이제이션 할 벡터(코드상 dp 변수) 에 어떤 값을 저장할 것이고 인덱스는 어떤 것을 의미할지 정의를 한다. 여기서는 해당 변수의 인덱스는 가치의 합인 목표 돈를 의미한다.
2. 그리고 해당 인덱스에 들어있는 값은 그 목표 돈을 만들 수 있는 동전들의 최소의 조합 수다.
3. coins 를 입력 받은 후 가지고 있는 동전에 해당 하는 dp 배열의 값을 1로 저장한다. => 가지고 있는 동전과 일치하는 목표 금액을 만드는 동전의 갯수는 자기 자신이기 때문에 최소값은 1이다.
4. 다른 dp 배열의 값들을 가장 큰 수 (보통은 INF 로 const 선언) 로 저장한다.
5. Bottom-up 방식으로 구현하기 위해 coins 배열을 오름차순으로 정렬해준다. => 문제에는 오름차순으로 주어진다는 말이 없어서 혹시 몰라 소팅을 해주었다.
6. coins 배열의 가장 처음 값부터 목표 금액인 k 원 까지 최소값을 갱신해준다. 이 때, dp 의 인덱스를 하나씩 올리면서 기준으로 잡은 동전을 가지고 만들 수 있는 방법의 수에 대한 점화식을 세운다 => min(dp[j], dp[j-coins[i]]+1)
7. 만약, k가 가지고 있는 동전으로 만들 수 없는 값이라면 기존에 초기화한 최대값이 나오기 때문에 이 때는 -1 을 출력해준다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k; //동전 종류, 목표값
vector<int> coins;
vector<int> dp;

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

    cin >> n >> k;

    coins.resize(n+1);

    for(int i = 1; i <= n; i++) {
        int input;
        cin >> input;
        coins[i] = input;
    }

    dp.resize(k+1, 99999);

    sort(coins.begin(), coins.end());

    // 주어진 동전을 만들 수 있는 최소 방법은 1가지다. => 초기화
    for(int i = 1; i < coins.size(); i++) {
        dp[coins[i]] = 1;
    }

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

    if(dp[k] == 99999)
        cout << -1 << '\n';
    else
        cout << dp[k] << '\n';



    return 0;
}

 

결과