[S5] 거스름돈 : Java : 14916 - 그리디

문제

14916번: 거스름돈

 

 

풀이 생각

n을 5와 2로만 채울 때 가장 최소 동전의 개수를 구해야 하므로, 5를 기준으로 5 동전의 크기를 줄여나가면서 구한다.

 

 

 

코드

1. input()

 n을 입력 받는다.

  public void getInput() throws Exception {
        n = Integer.parseInt(br.readLine());
    }

 

 

2. solution()

예를 들어 18일 때 18 ÷ 5 = 3이므로 최대 5 동전의 개수는 3이다.

그 후 18 - (5 X 3) = 3(나머지수)을 2 동전으로 채울 수 있는지 확인한다.

만약 나머지 수를 2로 채울 수 있다면 결과에 3 ÷ 2 = 1 의 값을 더해주고,

그렇지 않다면 5 동전의 수를 2로 줄여 동전의 수가 0이 될 때까지 같은 로직을 반복한다.

5 동전의 크기가 -1 이 되면 2와 5 동전으로 교환할 수 없다는 의미이고 -1을 리턴한다.

public void solution(){
        int remainValue;
        count = n/5;
        while(count >= 0){
            remainValue = n - (5*count);
            if(remainValue % 2 == 0){
                count += remainValue/2;
                break;
            }
            else{
                count--;
            }
        }
    }

 

 

3. print()

결과값 count를 출력한다.

public void print(){
        System.out.println(count);
    }

 

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class boj_14916 {

    public static BufferedReader br;
    public int n;
    public int count;

    public boj_14916(){
        if(br == null){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        count = 0;
    }

    public void run() throws Exception{
        getInput();
        solution();
        print();
    }

    public void getInput() throws Exception {
        n = Integer.parseInt(br.readLine());
    }

    public void solution(){
        int remainValue;
        count = n/5;
        while(count >= 0){
            remainValue = n - (5*count);
            if(remainValue % 2 == 0){
                count += remainValue/2;
                break;
            }
            else{
                count--;
            }
        }
    }

    public void print(){
        System.out.println(count);
    }
    public static void main(String[] args) throws Exception{
        new boj_14916().run();
    }
}

 

 

+++

멋진 선배님의 블로그를 참고하여 한 함수내에서 구현했던 방법에서 함수로 쪼개는 방법으로 구현해봤다.

확실히 코드가 눈에 잘 들어온다..! 최고!!