greedy

개요

---

이번 포스팅에선 알고리즘의 탐욕법(greedy), 완전탐색(brute force)에 대해 알아보도록 하겠다.

탐욕법(greedy)

---

문제 풀이를 위한 아이디어를 추출하고, 정당한지 확인하자.

특징

1. 문제 풀이를 위한 아이디어를 추출한다.
2. 추출된 아이디어가 문제 상황에 적합한지 판단 후 적용한다.

예시문제 거스름돈 문제

5585번: 거스름돈

---

조건

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

---

SOL

위 문제의 조건을 통해 우리는 1000엔에서 입력받은 금액을 뺀 거스름 돈을 추출하면 되는 것이다.

단. 최소한의 동전을 이용하여..

• 문제풀이를 위한 아이디어 추출
  • 큰 단위의 동전부터 거슬러 주기
• 추출된 아이디어가 문제 상황에 정단한지 판단 후 적용
  • 주어진 동전간의 관계는 각각의 배수로 이루어져 있기에 정당하다.

구현

---

#include <iostream>

using namespace std;
/* 
동전 500, 100, 50, 10, 5, 1
존재할 때 거스름돈을 만들 수 있는
최소한의 동전의 개수를 구하여라.

동전들의 관계를 보았을 때 서로 배수가 되는것을 
확인 할 수 있다. 
이를 통해 큰 동전의 개수부터 구하는 방법을 이용하면
문제를 해결할 수 있을 것이다. 
*/

int main()
{ 
    int num; 
    // 거스름돈 입력 
    cin >> num;
    // 동전의 개수 
    num = 1000 - num;
    int answer = 0;
    int coin[6] = {500, 100, 50, 10, 5, 1};
    for(int i=0 ; i < 6; i++)
    {   
        int tmp = num / coin[i];
        num -= (num / coin[i]) * coin[i];
        if(num != 0)
            answer += tmp; 
        else
        {
            answer += tmp;
            break;
        }     
    }
    cout << answer;
    return 0;
}

Reference

---

(이코테 2021 강의 몰아보기) 2. 그리디 & 구현