[백준] 11047.cpp : 동전 0

www.acmicpc.net/problem/11047

11047번: 동전 0

#include <iostream>

using namespace std;

int n, k;
int coins[10];

int main(void)
{
    cin >> n >> k;
    for(int i = n - 1 ; i >= 0 ; i--)   // 내림차순으로 정렬
    {
        cin >> coins[i];
    }
    int number = 0;
    for(int i = 0, cur ; i < n ; i++)   // 큰것부터 빼나감
    {
        cur = coins[i];
        while(k)                        // 목표값까지 뺴는데
        {
            if(k - cur < 0) break;      // 더 뺄 수 없을 때 까지
            k -= cur;                   // 빼주고
            number++;                   // 동전 갯수 1 증가
        }
    }
    cout << number << '\n';
}

 

[Approach]

1. 처음 값을 무조건 1부터 해서 배수로 주고 있으니, 그리디하게 큰 값부터 쭉 빼면서 내려오면 될 것 같다.

 

[Point]

1. 생각나는대로 작성하니까 바로 된다... 왜 실버1 인지는 잘 모르겠다.

2. 이것도 while 문으로 쭉 빼지 말고 그냥 나누기랑 나머지 연산 하면 되었던 것을...자주 이런다