[코테] 백준 5585번 : 거스름돈 (java)

❓문제

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

5585번: 거스름돈

 

---

🔅해석

이 문제는 사칙연산만 잘하면 풀 수 있는 문제이다.

이런 잔돈 계산 문제는 늘 계산식이 비슷하니 한문제만 풀면 다른 잔돈 문제를 어렵지않게 풀 수 있을 것이다.

 

잔돈의 개수를 최소한으로 받아야하므로 잔돈 중 제일 큰 잔돈을 먼저 계산하여 잔돈의 부피를 줄여야 한다. 

 

1. 받을 잔돈에서 제일 큰 잔돈의 개수를 구한다.

예를 들어, 380원 구매하고 1000원을 냈으면 620원의 잔돈이 생긴다. 이 중에서 500원의 개수를 구한다. 620원에서 500원을 나누면 몫 1이 나오는데 이는 620원에서 500원을 1번 받는다는 의미이다.

 

2. 몫이 1 이상이라면, 받을 잔돈에서 (n번째 잔돈 * 횟수)를 차감한다.

이는, 620 - (500 * 1)를 의미한다. 이러면 받을 잔돈이 120원으로 줄어든다.

 

이렇게 1,2를 반복하다보면 500원 1번, 100원 1번, 10원 2번 총 4번의 개수가 계산되는 것을 볼 수 있다.  

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
//거스름돈
// 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
// 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔
//input: 380
//output : 4
	
	public static void main(String[] args) throws Exception {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//620 = 500 + 100 + 10 +10
		int N = 1000 - Integer.parseInt(br.readLine());		//받을 잔돈
		int result = 0;	//받을 잔돈의 개수
		int[] changeList = {500, 100, 50, 10, 5, 1};	//잔돈 리스트
		
		while(N > 0) {		//받을 잔돈이 0보다 클때
			for (int i=0; i<changeList.length; i++) {		//잔돈 리스트 중에서
				if (N / changeList[i] >= 1) {				//받을 잔돈에서 n번째의 잔돈을 1회이상 받을 수 있다면
					result += N / changeList[i];			//받을 잔돈의 개수를 추가해주고
					N -= changeList[i] * (N / changeList[i]);	//받을 잔돈에서 차감한다.
					if (N <= 0) {							// 위 과정에서 받을 잔돈이 0이하가 되었다면 중지한다.
						break;
					}
				}
			}
		}
		System.out.println(result);
		
	}
}

 

---

❗결과