[c++]백준 11047 동전 0

www.acmicpc.net/problem/11047

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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이 

1.동전을 크기순으로 정렬(이 문제에서는 이미 정렬이 되어 있어서 따로 정렬이 필요 없다.)

2.동전 큰 것 부터 나누어서 몫이 있는 지 채크

3.몫이 있을 경우 K원에서 동전*몫 만큼 빼 줌

4.구한 몫을 count에 더해 줌

5.동전의 종류가 가장 작은 것까지 채크 해주면 됨.

 

코드

#include <iostream>

using namespace std;

int main(){

	int N, K;
	int A[11];
	int i, count=0, tmp = 0;
	cin >> N >> K;

	for( int i =0; i < N; i++){
		cin >> A[i];
	}

	for(i = N-1; i >=0; i--){
		if ( tmp = K/A[i] ){
			K -= K/A[i] * A[i];
			count += tmp;
		}
	}
	//cout << "i, K, tmp, count : " << i << ' ' << K << ' ' << tmp << ' ' << count << endl;

	cout << count << endl;
	return 0;
}