[백준 5585 c++] 거스름돈

문제 링크

www.acmicpc.net/problem/5585

5585번: 거스름돈

 

문제 접근

// 접근: 거스름돈 최소 동전개수 -> 그리디

 

문제 풀이

// 풀이: 그리디 알고리즘으로 큰 동전부터 나누어 가면서 동전의 개수 카운트

 

주의

 

 

개념

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>

// [백준 5585 c++] 거스름돈
// 접근: 거스름돈 최소 동전개수 -> 그리디
// 풀이: 그리디 알고리즘으로 큰 동전부터 나누어 가면서 동전의 개수 카운트
using namespace std; // cin,cout 편하게 사용 라이브러리

int main()
{
	// IO 속도 향상
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int price;
	cin >> price;
	int changes = 1000 - price;
	int count = changes/500;
	changes %= 500;
	count += changes / 100;
	changes %= 100;
	count += changes / 50;
	changes %= 50;
	count += changes / 10;
	changes %= 10;
	count += changes / 5;
	changes %= 5;
	count += changes / 1;
	changes %= 1;

	cout << count;
	 return 0;
}