[C++풀이] 11047번. 동전 0

 

문제 분석

그리디 알고리즘 문제이다. 이 문제로 처음 접했는데, 그 순간의 최적의 해를 구하는 알고리즘이다.

보통 위와 같이 '최대한 적은~ 최대한 많은~' 이런 문제형태로 나온다고 한다.

 

이 문제 역시 가장 적은 동전 개수로 k를 구하는 문제이다.

벡터에 동전가치들을 넣고, for문으로 k를 나눈 몫과 나머지를 계속해서 구하면 된다.

 

알고리즘 설계

int형 벡터를 이용해 동전 가치를 입력받아 초기화한다.

 

벡터의 끝부터 k를 나눠본다.

나눈 몫은 동전의 개수가 되므로 coin에 누적해서 쌓고, 

나눈 나머지는 새로운 k로 넣어주는 방식으로 계속해서 k를 나눈다.

 

만약 k가 0이 되면 break로 반복문을 탈출한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
/*
그리디 알고리즘
1. 동전종류n와 만들어야하는 수k 를 입력받는다
2. 동전의 가치를 입력받는다
3. k원을 최소한의 동전으로 구현한다
4. 동전개수를 출력한다.
*/
int main() {
    //1
    int n, k;
    cin >> n >> k;

    //2
    vector <int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    //3
    int coin = 0;
    for (int j = n - 1; j >= 0; j--) {        
            coin += (k / v[j]);
            k = k % v[j];        
        if (k == 0) {
            //cout << "Coin개수: " << coin << '\n';
            break;
        }        
    }
    cout << coin << '\n';
    return 0;
}

 

느낀 점

처음에는 벡터의 0 인덱스부터 시작해서 v[i]>k 가 되는 순간의 v[i-1]로 위의 과정을 시도했다. 그러나 이 경우에는 벡터가 작은 것->큰 것으로 올라가기때문에 오히려 계산이 복잡해졌다.

그래서 벡터를 거꾸로 큰 인덱스부터 내려오면서 계산을 하니 코드가 훨씬 간편해졌다.

 

그리디 알고리즘이라는 용어도 처음 접했는데, 지금까지 풀었던 문제에도 적용했던 개념이었다.

앞으로는 알고리즘 공부도 시작해야겠다.