[기본문제풀이] greedy 알고리즘

 

풀이 일시 : 2020-08-29

​

그리디알고리즘 :

당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다.

대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다.

​

문제 :

총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라

​

풀이 :

가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다.

#include <iostream>

using namespace std;

//총 몇개의 동전을 거슬러 줘야되는가
int main() {
	int n, result = 0;
	cin >> n;
	result += n / 500;
	n %= 500; //나머지 연산을 해서 다음 레이어로 간다.
	result += n / 100;
	n %= 100;
	result += n / 50;
	n %= 50;
	result += n / 10;
	cout << result;
	return 0;
}