[백준] 11047번 : 동전 0 - 자바(JAVA)

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

11047번: 동전 0

 

문제 해석

준규는 동전을 많이 가지고 있는데 동전의 종류는 총 N이다.
동전을 적절히 사용하여 그 가치의 합을 K로 만드려고 한다. 이때 필요한 동전의 개수의 최솟값을 구하라.

 

입력

첫째 줄에  N과 K가 주어진다.

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다.

 

제약조건

1 ≤ N ≤ 10

1 ≤ K ≤ 100,000,000

1 ≤ Ai ≤ 1,000,000, A1 = 1

i ≥ 2인 경우에 Ai는 Ai-1의 배수

 

출력

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

 

문제 풀이 전 설계

동전의 가치가 배수로 주어지기 때문에 가치가 큰 동전을 사용해야지 동전 개수를 최소로 구할 수 있다.

 

만약 50000원을 예시로 들었을 때

50000원짜리 동전이 1개 필요하다면

10000원짜리 동전은 5개 필요하다.

5000원짜리 동전은 10개 필요하다.

최악의 경우 1원짜리 동전은 50000개 필요하다.

 

따라서 가치가 큰 동전부터 탐색을 하며 K원을 만들어야 한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class CoinZero {

	static int kindOfCoin;
	static int sumOfValues;
	static int coinCount;
	static int[] coinArray;

	public static void main(String[] args) throws IOException {

		inputCoinInfo();
		getCoinCount();
		printCoinCount();

	}

	private static void inputCoinInfo() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		kindOfCoin = Integer.parseInt(st.nextToken());
		sumOfValues = Integer.parseInt(st.nextToken());
		coinCount = 0;
		coinArray = new int[kindOfCoin];

		for (int i = 0; i < kindOfCoin; i++) {
			coinArray[i] = Integer.parseInt(br.readLine());
		}
	}

	private static void getCoinCount() {

		while (sumOfValues != 0) {

			for (int i = kindOfCoin - 1; i >= 0; i--) {

				if (sumOfValues < coinArray[i]) {
					continue;
				}

				sumOfValues -= coinArray[i];
				coinCount++;
				kindOfCoin = i + 1;
				break;
			}
		}
	}

	private static void printCoinCount() throws IOException {

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(coinCount + "\n");
		bw.flush();
		bw.close();

	}

}

최적화를 위해서 kindOfCoin = i + 1; 구문을 추가하였습니다.

 

이를 통해 한번 1000원이 쓰이게 되면 이는 1000원을 초과하는 동전을 더 이상 사용할 수 없음을 의미하기 때문에 1000원 이하만 탐색합니다.