[백준 11047번] 동전 0

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

11047번: 동전 0

풀이) 

정말 간단한 문제였는데, 문제를 잘못이해해서 시간이 오래걸린 문제이다. 'Ai는 Ai-1의 배수' 이 조건을 생각하지못했어서 100 1000 1100 동전으로 2000원 만드는 반례를 혼자 만들어보고 오래 고민해보고 있었다. 로직 자체는 간단하게 큰 동전부터 많이 채우면 해결된다.

#include <iostream>
using namespace std;

int n, k, cnt;
int coin[10];

int main()
{
	cin >> n >> k;
    for (int i = 0; i < n; i++) 
		cin >> coin[i];
    for (int i = n - 1; i >= 0 && k != 0; i--) 
        if (coin[i] <= k) {
            cnt += k / coin[i];
            k -= k / coin[i] * coin[i];
        }
	cout << cnt;
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!