[C++] 백준 2294 : 동전 2

문제

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

 

풀이

 dp[i]에 i원을 만들기 위한 최소 동전의 개수를 저장하면서 dp[k]의 값을 구한다.

 

 dp[i] = min(dp[i], dp[i-coin[j]]+1);

 

 예를 들어, coin 입력이 12 10 8 7 3 2 이렇게 들어왔을 때, 

• dp[0] = 0
• dp[1] 은 만들 수 없으므로 INF
• dp[2] 는 min(dp[2], dp[2-coin[5]+1)
  • 0원을 만드는 데 필요한 동전 개수(=0) 에 coin[5]를 한 번 추가(=2원을 추가)해준다.
• 위와 같은 과정을 반복하면서, 다음 값들을 비교하며 최솟값을 dp[i]에 저장한다.
• dp[5]
  • 초기값은 INF
  • dp[5-coin[4]]+1
    • dp[5-coin[4]] = dp[5-3] = dp[2] . 즉. 2원을 만드는 데에 필요한 최소 동전 개수.
    • 여기에 3원을 하나 더해주면 됨.(=+1)
  • dp[5-coin[5]]+1
    • 초기값은 INF
    • dp[5-coin[5]] = dp[5-2] = dp[3]. 즉 3원을 만드는 데에 필요한 최소 동전 개수.
    • 여기에 coin[5]=2원을 하나 더해주면 됨. (= +1)

 

 

코드

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int n,k, ans = 1000000;
int coin[100];
int dp[100002];
set<int, greater<int>> s;
int main()
{
    cin >> n >> k;
    for(int i=0; i<n; i++) {
        int c;
        cin >> c;
        s.insert(c);
    }
    
    //중복 제거 내림차순 정렬 
    n = s.size();
    int idx=0;
    for(int num : s){
        coin[idx++] = num;
    }
    
    // dp를 INF 값으로 초기화. 이 경우 1000000 로 초기화.
    for(int i=1; i<=100000; i++){
        dp[i] = 1000000;
    }
    
    // dp 값 계산
    for(int i=1; i<=k; i++){
        for(int j=0; j<n; j++){
            if(i-coin[j]>=0 && dp[i - coin[j]] != 1000000 ){
                dp[i] = min(dp[i], dp[i-coin[j]]+1);
            }
        }
    }
    
    if(dp[k] == 1000000) {
        cout << "-1" << "\n";
        return 0;
    }
    cout << dp[k]<< "\n";

    return 0;
}

 

 

메모

처음에 그리디로 푸려다가.. 많이 해메고.. 조금 이상하게 접근했다가.. 해메고~~