[백준] 11047번 그리디 알고리즘 - 동전0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

 

(구상)

 입력 

: 버퍼리더를 통해 입력을 받음

스트링 토크나이져를 통해 첫줄에 입력받은 값을 int N,M에 담음 

N : 동전의 종류의수 , M :금액 을 받는다. 

int arr[] 배열에 동전의 종류를 입력받는다. 동전의 금액별로 오름차순으로 배열안에 담긴다. 

 

돈을 동전으로 어떻게 계산할 것인가 ? 

예를들어 4600원이고 동전의 종류는 (5000, 1000, 500, 100, 10) 라고 하자. 

총금액보다 동전은 금액이 작아야 한다. 

그러므로 조건을  "금액 <= 동전 " 이라고 주고 이때 위의 예에서는 1000원짜리 4장으로 4천원을 낼 수 있다. 

이는 총금액/동전을한 몫 =4 이므로 4장을 쓸수 있다는 것을 알수있다. 

또한 총금액/동전 : 사용한 동전의 갯수, 총금액/동전 * 동전의 금액   : 해당 동전으로 낼수있는금액 

(4600/1000 =4 이므로 1000짜리 4개를 사용하고, 4*1000 이므로 4000원을 낼 수 있다.)

그러면 낸 금액을 제외한 나머지 금액을 해당 동전보다 단위가 작은 동전들로 같은 방법으로 거듭 계산하면 된다. 

그리고 계산이 끝나면 0이 되므로  0이 될때의 동전의 수를 리턴해 주면 된다. 

 

 

 

구상한 바를 코드로 구현해 주었다. 

package codingTest;

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

public class Algoritm13 {
	public static void main(String[] args) throws Exception {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int arr[] = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}

		int money = M;
		int cnt = 0;

		for (int i = arr.length - 1; i >= 0; i--) {

			if (money >= arr[i]) {
				cnt += money / arr[i];
				money -= (arr[i] * (money / arr[i]));

				if (money == 0) {
					System.out.println(cnt);
					break;
				}
			}

		}

	}
}