[백준]11047번 동전 0 c/c++

문제

 

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

11047번: 동전 0

 

설명

 

• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식이다.
• 그리디 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

왜 그리디 알고리즘 인가??

 

이렇게 단순하게 거스름돈을 지불해야 하는 상황에서 큰 동전만을 생각하고 다른 동전은 생각하지 않기 때문에

 매순간 최적이라고 생각되는 경우를 선택하는 그리디 알고리즘이라고 할 수 있다.

 

 

코드

 

#include<iostream>
using namespace std;

int a[10];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int cnt = 0;
	for (int i = n - 1; i >= 0; i--) {  //가장 큰 동전부터 생각
		cnt += k / a[i]; //몫을 cnt값에 저장
		k %= a[i]; //나머지값을 k에 저장
	}
	cout << cnt;
	return 0;
}

 

그리디 알고리즘의 가장 대표적인 문제라고 할 수 있다.