[백준 : 실버2] 동전 0 : 그리디 알고리즘(Java)

이번 문제는 생각외로 정말 쉬웠다.

 

문제부터 살펴보자.

 

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

 

문제 접근

 

나는 이번문제를 어떻게 접근 했냐면 일단 가장 적은 동전의 수를 사용하려면

일단 수가 가장큰거부터 나눠야 한다고 생각을 했다.

 

 

따라서 가장 마지막수에 먼저 접근을 해서 몫이 1이상인 시점부터 동전의 수를 올리고 나머지를 가지고 나누는것으로 했다.

 

아마 소스를 보면 바로 이해가 갈것이다.

 

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("가지고 있는 동전 종류 수와 맞출 가격을 입력하시오");
		int kind = sc.nextInt();
		int sum = sc.nextInt();
		
		int[] coins = new int[kind];
		
		System.out.println("동전의 가치를 차례대로 오름차순으로 입력하시오");
		for(int i = 0; i<kind;i++) {
			coins[i] = sc.nextInt();
		}
		
//		int kind = 10;
//		int sum = 4790;
//		
//		int[] coins = {1,5,10,50,100,500,1000,5000,10000,50000};
		
		System.out.println(makeCount(sum,coins));
		
	}

	private static int makeCount(int sum, int[] coins) {
		// TODO Auto-generated method stub
		int count = 0;
		
		for(int i = coins.length-1; i>=0;i--) { //동전에 접근
			if(sum == 0)
				break;
			if(sum/coins[i]>=1) { //나눴을때 몫이 1이상이면 접근
				count += sum/coins[i]; //동전 개수 올리고
				sum%=coins[i]; //지폐를 나머지 값으로 업데이트
			}
		}
		
		return count;
	}
	
}

 

 

여기서 성능을 좀더 좋게 하고 싶다면 Scanner 대신 BufferedReader를 사용하면 된다.