03.04. 동전 0[Greedy Algorithm][백준 11047]

 

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

11047번: 동전 0

 

Algorithm classification : Greedy Algorithm

 

03.04.1. Problem

N and K are given in the first line. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) From the second row to the N rows, the coin values ​​Ai are given in ascending order. (If 1 ≤ A_i ≤ 1,000,000, A_1 = 1, and i ≥ 2, then A_i is a multiple of A_(i-1))

 

03.04.2. Input limit

11 lines are given as the input. The i-th line contains two space-separated integers, D_i and V_i, where D_i is the amount of minutes required to solve the i-th problem, and Vi$V_i$ is the number of incorrect verdicts on the i-th problem.

For each i, 1≤D_i and 0≤V_i≤1 000. Also, ∑i from 1 to 11 : D_i ≤ 300.

 

03.04.3. Output

In the first line, we print the minimum number of coins required to make K won.

 

03.04.4. Solution

그리디 알고리즘에 대해 전반적으로 소개한 포스팅에서 다룬 문제입니다. 굉장히 유명한 문제죠. 큰 액수의 동전들로 나누고 나머지에 대해서 작은 액수의 동전으로 다시 같은 작업을 반복하는 과정을 거치면 됩니다.

	int data[n], i, c = 0;
	for(i = 0;i < n;i++){
		scanf("%d", &data[i]);
	}
	sort(data, data+n);
	
	for(i = n-1; sum; i--){
		c += sum/data[i];
		sum %= data[i];
	}