[백준] 알고리즘 분류(그리디 알고리즘,JAVA)14916번, 거스름돈

문제 링크

14916번: 거스름돈

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 거스름돈 n원을 동전 2원과 5원으로 거슬러 주는 동전의 최소 개수를 결과로 출력합니다.

2. 동전 2원과 5원은 무한정 가지고 있습니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 5원을 거슬러 주는 개수를 내림차순으로 탐색합니다.

 

3. 탐색 중 2원과 더불어 거슬러 줄 때 동전의 개수를 결과로 출력합니다. 

 

 

동전 거슬러 주기.

 

5원을 거슬러 줄 수 있는 최대 개수부터 탐색합니다.

 

예를 들어.

거스름 돈 : 18일 때

 

5원으로 거슬러 줄 수 있는 최대 개수 : 18 ÷ 5 = 3개

 

5원을 3개로 거슬러 줄 때18 % 5 = 3원3원은 2원으로 거슬러 줄 수 없으므로 실패!

 

5원을 2개로 거슬러 줄 때

18 % 5 + 5 = 8원

8원은 2원 4개로 거슬러 줄 수 있으므로 성공!

 

5원 : 2개

2원 : 4개

거슬러 줄 수 있습니다.

 

※ 5원 1개일 때를 탐색하지 않는 이유는 거슬러 줄 수 있더라도 2원을 사용하는 횟수가 증가하기 때문에 동전의 최소 개수가 될 수 없습니다.

 

결과적으로 5원으로 거슬러 줄 수 있는 개수를 내림차순으로 탐색하여 가장 먼저 거슬러 줄 때 동전의 개수가 최소 개수가 됩니다.

예제입력1.

1. 입력된 정보를 저장합니다.

 

거스름 돈 : 13

 

2. 5원을 거슬러 주는 개수를 내림차순으로 탐색합니다.

 

5원으로 거슬러 줄 수 있는 최대 개수 : 13 ÷ 5 = 2개

 

5원을 2개로 거슬러 줄 때

13 % 5 = 3원

3원은 2원으로 거슬러 줄 수 없으므로 실패!

 

5원을 1개로 거슬러 줄 때

13 % 5 + 5 = 8원

8원은 2원 4개로 거슬러 줄 수 있으므로 성공!

 

5원 : 1개

2원 : 4개

거슬러 줄 수 있습니다.

 

3. 동전의 최소 개수를 결과로 출력합니다. 

최소 개수 : 1(5원) + 4(2원) = 5

5개를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 거스름 돈을 5원으로 줄 수 있는 개수를 내림차순 기준 탐색합니다.
• 가장 먼저 5원과 2원으로 나누어 떨어질 때 동전의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int answer = -1;
        int N = Integer.parseInt(br.readLine());
        //5원을 사용할 수 있는 횟수 기준 내림차순 탐색
        for(int i=N/5;i>=0;i--){
            if((N - (5 * i))%2 == 0){	//5원을 i개 쓰고 2원으로 거스를 수 있을 때
                answer = i + (N - (5 * i))/2;	//동전의 개수 저장
                break;	//가장 먼저 거슬러 줄 때가 최소 개수
            }
        }
        bw.write(answer + "");		//최소 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}