#[C++]11047 - 동전 0

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

11047번: 동전 0

---

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

코드

using namespace std;
#include <iostream>
#include <vector>

int main()
{
    int n, k;
    cin >> n >> k;
    
    int cnt=0;
    vector<int> A;
    
    for(int j=0; j<n; j++) {
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }
    
    for (int i =n-1; i>=0; i--) {
        if(A[i] <= k) {
            int z=0;
            z= k/A[i];
            cnt += z;
            k = k-z*A[i];
        }
    }


    cout << cnt << "\n";
    return 0;
}

 

 

 

그리디 알고리즘 너무 어렵다.

가장 효율적으로 최적 해를 찾아야함..

어려워요

 

---

using namespace std;
#include <iostream>
#include <vector>

int main()
{
    int n, k;
    cin >> n >> k;
    
    int cnt=0;
    vector<int> A;
    
    for(int j=0; j<n; ++j) {
        cin >> A[j];
    }
    
    int i=0;
    
    while(k != 0 && i<n) {
       // cout << "i : "<< i << " ";
        if(A[i] <= k && A[i+1] > k) {
            int z =0;
            z = k/A[i];
            cnt += z;
            k -= A[i]*z;
           // cout << "K is " << k << "\n";
           // cout << cnt << " ";
            i =0;
            continue;
        }
        i++;
    }

    cout << cnt << "\n";
    return 0;
}

이건 제일 처음에 짠 코드

그리디알고리즘을 사용하지도 않았고

엄청 비효율적이긴 하지만 출력값이 잘 나오긴 한다.

근데 백준에서는 틀렸다고 뜸.. 왜..??