[코드업] 3301 : 거스름돈 (C)

알고리즘

그리디

힌트

가장 비싼 화폐부터 거슬러 준다.

 

풀이

이 문제는 대표적인 그리디 문제다.

거슬러 줄 수 있는 가장 비싼 화폐부터 거슬러 주면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include<iostream> using namespace std;   int main(){     int money[8]={10,50,100,500,1000,5000,10000,50000};          int n,cnt=0;     cin>>n;          for(int i=7;i>=0;i--){         cnt+=n/money[i];         n%=money[i];     }          cout<<cnt;      }