[Codeforces] 996A - Hit the Lottery

https://codeforces.com/problemset/problem/996/A

Problem - 996A - Codeforces

문제

Allen은 많은 돈을 가지고 있다. 그는 은행에 n 달러를 가지고 있다. 그는 보안상의 이유로 현금으로 인출하기를 원한다.(우리는 여기에 이유를 공개하지 않을 것이다.) 달러 지폐의 액수는 1, 5, 10, 20, 100이다. 앨런이 잔금을 전부 인출한 후 받을 수 있는 최소한의 지폐 갯수는 몇개인가?

 

Note

첫 번째 샘플 사례에서 앨런은 100달러 지폐, 20달러 지폐, 5달러 지폐로 이것을 인출할 수 있다. 앨런이 한 장 혹은 두 장의 지폐로 125달러를 받을 방법은 없다.

두 번째 샘플 사례에서 앨런은 20달러 지폐 2장과 1달러 지폐 3장을 인출할 수 있다.

세 번째 샘플 사례에서 앨런은 100,000달러 지폐를 인출할 수 있다.

---

 

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());	// 출금 금액
		int count = 0;	// 사용할 지폐 수
		int[] arr = {100, 20, 10, 5, 1};	// dollar biils
		
		for(int i=0; i<arr.length; i++) {
			count += n / arr[i];		// 각 지폐별 갯수
			n -= arr[i] * (n/arr[i]);	// 다음 지폐를 구하기 위해 나눔
		}
		
		System.out.println(count);
		bf.close();
	}

}

풀이

각 지폐를 배열로 저장하고, 각각의 지폐를 사용할 수 있는 갯수를 카운트 한다.

그 후 사용된 금액만큼 현재금액에서 빼고, 다음 지폐를 카운트 한다.