[Day14]JAVA 백준 거스름돈(14916번)

https://www.acmicpc.net/problem/14916

 

 

 

백준 거스름돈을 풀기 위해서는 Greedy(탐욕법)을 활용해서 풀 수 있다. 

 

Greedy 란 각 단계에서 최적의 선택을 하는 것인데 쉽게 생각하면 최적의 선택을 할 수 있는 규칙을 찾아내는 것이라고 생각하면 된다. 

 

Greedy 의 대표 문제라고 할 수 있는 거스름돈은 큰 범위의 돈부터 거슬러줘서 최소의 동전을 사용하게 만드는게 최적의 방법입니다. 

 

거스름 동전을 2원,5원으로만 준다고 하였으니 5원부터 주고 나머지 2원으로 주면 되겠다! 

라고 생각하면 바로 다시 문제를 천천히 일어 보길 바란다. 

 

13원일때 5원 1개 , 2원 4개  총 5개를 줘야 동전의 개수가 최소가 되는 것이다. 

보통 13원이라고 하면 
13/5 = 2 ,  5원 2개 주고 3원 중 2원으로 1개 주고 1원이 남으면 거슬러 주지 못하네? 라고 생각할 수 있다. 

 

문제에서 친절히 예시를 주며 최소의 동전의 개수를 만들기 전에 어떻게든 동전을 거슬러 줄 수 있는 것이 최적의 선택인 것이다. 

 

어떻게 하면 5원을 최대로 많이 쓸 수 있을까? 

 

찔금찔금 거스름은 2원씩 주면서 나머지 금액이 5의 배수가 되는지 확인하는 것이다. 

13원
1. 13 - 2 = 11원 
2. 11 - 2 = 9
3. 9 - 2 = 7
4. 7 - 2 = 5 (5의배수)
5. 5 - 5 = 0 

총 5개의 동전을 사용

 

 

*최종코드

import java.io.*;
public class Main{ 
  public static void main(String[] args) throws IOException
  {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      Integer n = Integer.parseInt(br.readLine());

      int coin =0;

      //5의 약수인지 확인
      if(n%5 ==0)
      {
        System.out.println(n/5);
        return;
      }
      else
      {
        while(n >0)
        {
          n -=2;
          coin++;
          if(n%5 == 0)
          {
            coin += (n/5); //2원
            break;
          }
        }

        if(n<0)
          coin = -1;          
      }      

      System.out.println(coin);
    }
}