백준 11047_동전 0.cpp

<소스코드>

#include <iostream>
using namespace std;
int main(){
    int n, k;
    int cnt = 0;
    cin >> n >> k;
    int coin[n];
    for(int i = 0; i < n; i++){
        cin >> coin[i];
    }
    for(int j = n-1; j >= 0; j--){
        if(coin[j] <= k){
            while(coin[j] <= k){
                k -= coin[j];
                cnt++;
            }
        }
        if(k == 0) { break;}
    }
    cout << cnt << endl;
    return 0;
}

1. 변수&함수
   int n : 동전의 개수
   int k : 만들어야 동전의 가치
   int coin[n] : 동전의 종류 리스트
   int cnt : 동전의 개수

2. 알고리즘
   ※탐욕법 문제이다!
   1) 가장 큰 값부터 k와 비교를 하면서
   -k보다 크면 넘기고
   -k보다 작으면 그 값이 k보다 커질때까지 빼주면서 동전의 개수를 더해준다.
   2) k가 0원이 되면 동전의 개수를 출력해준다.

3. 배운점
   탐욕법을 연습하기 가장 easy한 문제였다.

4. 아쉬운점&느낀점
   탐욕법이라는 것을 알고 푸니까 정말로 쉽게 보였고, 이래서 알고리즘의 종류를 많이 알고 있어야 됨을 느끼게 되었다.