[BAEKJOON]14916 거스름돈

문제 요약

• 알고리즘 분류: 그리디
• 난이도:  Silver5
• 문제내용:
  • 2원, 5원 동전으로 거스름 돈을 줄수 있다.
  • 거스름돈이 N일때 최소 동전 개수를 구하여라(안되면 -1로 출력하여)

• 사이트: https://www.acmicpc.net/problem/14916

 

문제풀이

 이번 문제는 전체 경우의 수를 탐색하기에는 최대 거스름돈이 10만이라서 모든 경우의 수를 구하면 시간 초과가 나서 O(N) 탐색으로 푸는 방법을 찾아야 될것이다. 그래서 이번 문제는 그리디로 풀것이다. 그리디에 대한 설명은아래글로 확인 해보면 된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근 방법

 그리디 같은 문제는 구현 보다 사고력을 요구하는 문제이다. 그래서 구현보다 어떻게 접근하는지만 알면 된다.  이번 문제에서 5원 기준으로 최대치만 구하면다.  그러기 위해서 5원 최대 가능한 개수를 구하기 위해서는 조건이 5를 나누었을때 정수가 되면 된다. 그러기 위해서는 처음부터 5원 나누면 안되고 2원에서 계속 차감해서 5를 나누어 정수가 죄는 조건만 구하면 된다. 만약에 계속 2원 차감해도 5로 나누어도 정수가 안되거나 또는 0이 안되면 -1 출력만 하면 끝이다. 설명 만으로 이해가 되기 힘드니 예제 13 가지고 설명 하겠다.

1. 13, count = 0
2. 11, count = 1
3. 9, coount = 2
4. 7 count = 3
5. 5 count = 4 <-- 5와 나누면 나머지가 0이 된다.,
6. 0 count = 5
답은 5개이다.

 위에 예제 처럼 계속 2를 차감해서 5를 나누어서 나머지가 0일때 까지 계속 탐색만 하면 끝이다. 나머지 구현 부분은 코드로 구현 하면된다.

마무리

 위와 같이 구현했을때 시간 복잡도는 O(N)이하만큼 나온다. 그리고 코드 보면 구현은 쉽게 되어 있지만 답이 나오는데 시간이 오래 걸린다고 볼수 있다.

 

Code

Python

N = int(input())

count = 0
while N > 0:
    if N % 5 == 0:
        count += N // 5
        break
    else:
        count += 1
        N -= 2

print( count if N >= 0 else -1)

Java

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

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 count = 0;

		while (N > 0){
			if(N % 5 == 0){
				count += N / 5;
				break;
			}else{
				count++;
				N -= 2;
			}
		}

		System.out.println(N >= 0? count : -1);
	}
}