링크 | https://www.acmicpc.net/problem/5585
문제 |
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
입력 |
입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.
출력 |
제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.
예제 |
Solution |
-
그리디 알고리즘(욕심쟁이 알고리즘): 매 선택에서 가장 최적의 선택을 하여 적절한 답을 찾아가는 설계 기법.
-
해당 문제가 그리디 알고리즘이 성립하는 이유: 500, 100, 50, 10, 5, 1엔짜리 동전들은 반드시 큰 쪽이 작은 쪽 액수의 배수이다.
큰 수의 약수들로 큰 수를 만들 수 있다면, 큰 액수의 동전으로 교체했을 때 항상 동전의 개수를 줄일 수 있게 된다. 만약 배수가 아니라면 그리디 알고리즘을 더이상 사용할 수 없게 된다.
ex) 500, 400, 100일때 800엔의 거스름돈을 주는 경우 500, 100x3로 이뤄지만 동전 4개가 되지만, 400x2로 구성하면 동전 2개가 된다. 이 경우 그리디 알고리즘을 이용하여 500엔부터 세었을 때 최적의 값을 찾을 수 없게되므로 알고리즘을 사용할 수 없다.(다이나믹 알고리즘을 사용해야한다.)
- 가장 큰 화폐의 단위부터 돈을 거슬러 준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Change {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int c = 1000-Integer.parseInt(br.readLine());
int[] change = { 500, 100, 50, 10, 5, 1 };
int cnt=0;
for(int i : change) {
if (c/i > 0) {
cnt += c / i;
c = c % i;
}
i++;
}
System.out.println(cnt);
}
}
java