[개념] 그리디(Greedy) 알고리즘이란?

그리디(Greedy) 알고리즘이란?

1) 그리디(Greedy) 알고리즘 개념

    탐욕적 접근(한 가지만 보고 좇는다.)
    ㄴ무조건 작은거, 무조건 큰거, 무조건 긴거, 무조건 짧은거 먼저

2) 대표예시

   ㄴ 거스름돈 

    1990원 짜리를 받았을 때, 거스름돈 동전(500원, 100원, 50원, 10원)으로 돌려줄때 가장 최소로 주는 총 개수는?

    M1) 500원짜리 먼저 x 3개

    M2) 100원짜리 x 4개

 

    M3) 50원짜리 x 1개

 

    M3) 10원짜리 x 4개

 

답 : 12개(3+4+1+4)

---

 

#include <stdio.h>
#include <stdlib.h>
 
/*
 Q) 들어온 지폐를 가지고 동전(500원, 100원, 50원, 10원)으로
  거슬러 줄 때 최소한의 동전으로 거슬러줄 때, 최소개의 총 개수는?
*/
int main(){
    int inputNum, result = 0; // inputNum = 들어온 돈, result= 동전 총 개수
    scanf("%d", &inputNum);
 
    result += inputNum/500;
    inputNum%=500;
 
    result += inputNum/100;
    inputNum%=100;
 
    result += inputNum/50;
    inputNum%=50;
 
    result += inputNum/10;
 
    printf("%d", result);
 
    return 0;
}
 
// 그리디 알고리즘 최적해 보장 X시? - > 다이나믹 프로그래밍 알고리즘 //