백준 14196번 : 거스름돈

 

2원과 5원만 가지고 거스름돈을 최소한으로 주는 방법의 수를 구하는 문제이다.

 

13원 = 5원 1개, 2원 4개  = 5개

14원 = 5원 2개, 2원 2개 = 2개

23원 = 거스름돈을 딱 맞게 줄 수 없으므로 -1 리턴

 

 

거스름돈을 최소한으로 주기 위해서는 5원짜리로 최대한 많이 주어야만 한다.

그렇기 때문에, 5원을 최대한으로 주었을 때를 가장 먼저 계산해야 한다.

 

1. 거스름돈이 n이라 할때, 일단 n/5를 통해 가장 많이 줄 수 있는 5원의 개수를 구한다.

 

2. 1번에서 값이 딱 떨어진다면, 5원으로만 거스름돈을 줄 수 있기 때문에 해당 값이 최솟값일 것이다.

하지만, 여기에서 값이 떨어지지 않았다면 5원을 주고 남은 나머지 금액을 2원으로 줄 수 있는지 확인한다.

나머지가 모두 2원으로 떨어진다면, 이 경우가 최소한의 동전 개수를 구하는 방법일 것이다.

 

여기에서 준 5원의 개수는 n/5 즉, n을 5로 나누었을 때의 몫이다.

 n - n/5 가 5원으로 주고 나온 나머지 금액이고, 이 금액의 몫이 바로 줄 수 있는 2원의 개수이다.

결국, n/5 +  ( n-n/5)%2 의 값이 최소한의 동전일 것이다.

 

3. 하지만, 2번에서 딱 떨어지지 않을 수도 있다.

그럴 경우에는, 5원의 개수를 1개 감소시켜서 위의 방법을 반복하면서 가장 최소의 값을 찾아야 한다.

5원이 0일때까지 반복했는데도 딱 떨어지는 값이 없다면, 5원과 2원만으로는 거스름돈을 줄 수 없는 방법이므로 -1을 리턴하도록 한다.

 

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n  = sc.nextInt();
		int size = n/5;
        int result = -1;
     	for(int i=size;i>=0;i--){
          if((n-(5*i))%2==0){
          	result = i+(n-5*i)/2;
            break;
          }
      	}
		System.out.println(result);
	}
}

 

이 문제처럼 접근해서 풀어도 문제는 잘 풀릴 것 같으나, 위의 방식이 생각해내기가 쉬워 보인다..

dyii.tistory.com/2

백준 1463번 : 1로 만들기