[c++] 백준 11047 동전 0

백준 단계별로 풀어보기 [그리디 알고리즘] 동전 0

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

11047번: 동전 0

 

[풀이]

n개의 종류의 동전을 적절히 이용해서 가치의 합이 k가 되게하는 최소 동전의 개수를 구하는 문제이다. 오름차순으로 동전의 가치값을 입력했고, 최소 개수를 구하기 위해서는 가장 큰 가치값부터 시작해서 k를 채워나가면 된다. 따라서 그리디 알고리즘에 해당하고, k / val[n-1] 을 하여 k를 만들 수 있는 동전 개수 cnt를 가장 가치값이 큰 값부터 몇 개씩 이용 가능한지 구해 합해나갔다.  k -= val[n-1] * c 로 k의 값이 0이 될 때까지 반복문을 돌려 구한다.

 

[코드]

#include <iostream>
#include <algorithm>

int main() {
	int n, k, cnt = 0;
	std::cin >> n >> k;
	int* val = new int[n];
	for (int i = 0; i < n; i++) {
		std::cin >> val[i]; 
	}

	int c;
	while (k != 0) {
		c = k / val[n-1];
		cnt += k / val[n - 1];
		k -= val[n - 1] * c;
		n--;
	}

	std::cout << cnt;

	delete[] val;

	return 0;
}