[백준 14916] 거스름돈

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

14916번: 거스름돈

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

예제 입력 1 

13

예제 출력 1 

5

예제 입력 2 

14

예제 출력 2 

4

 

 

문제 분석

거스름돈 문제는 대표적인 그리디 문제입니다.

1. 동전의 개수가 최소가 되도록 거슬러 주어야 한다.
2. 만약 거슬러 줄 수 없다면 -1 출력합니다.

 

 

수도 코드

 / 와 %를 사용해서 구현해보겠습니다. 

변수 tmp : 계산된 n을 임시 저장할 변수

 

n / 5 → 5원의 개수 

tmp = n % 5 → 2원의 개수를 정하는 기준

if(!(tmp % 2 ==0)) → 2원으로 전부 거슬러 줄 수 없으므로 count 했던 5원의 개수 -1

 

n / 2 → 2원의 개수

tmp = n % 2

if(!(tmp==0)) → 5원과 2원으로 거슬러 줄 수 없으므로 -1 출력

 

 

이를 참고해서 코드를 구현해보겠습니다.

 

실패 코드

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		// 출력 count 선언 및 초기화
		int count = 0;
		// 임시변수 : n값 갱신을 위한 변수
		int tmp;
		
		count = n / 5;
		tmp = n % 5;
		if(!(tmp % 2 == 0)) count --;
		count = tmp / 2;
		tmp = n % 2;
		if(!(tmp == 0)) System.out.println(-1);
		else System.out.println(count);
	}

}

 

실패 원인 분석 : 

거슬러 줄 동전의 개수가 최소가 되기 위해서는 5원 동전 개수가 최대로 사용되어야 합니다.

 = 5원으로 거슬러 줄 수 없다면 거스름돈 -2를 한 후 다시 5원으로 거슬러 줄 수 있는지 확인하는 작업을

    반복해야 합니다.

 

성공 코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		// 거스름돈
		int n = kb.nextInt();
		// 출력 : 동전 개수 count 선언 및 초기화
		int count = 0;
		
        	// 거슬러줄 동전의 개수가 최소가 되기 위해서는 5원의 경우의 수부터 계산
		if(n % 5 == 0) System.out.println(n / 5);
		else {
			while(true) {
				if(n < 0) {
					System.out.println(-1);
					break;
				}
				if(n == 0) {
					System.out.println(count);
					break;
				}
				
				n -= 2;
				count++;
				
                		// n-2한 후 다시 5원으로 나누어 떨어지는 지 확인
				if(n % 5 == 0) {
					System.out.println(count += (n / 5));
					break;
				}	
			}
		}
				
	}
		
}

 

처음에는 break문을 전부 뺀 상태로 돌려서 무한대로 출력되는 에러가 발생하였습니다.

💡 반복문 사용 시 적절히 break문 기재!