[백준/BOJ] 11047번 c++ 문제풀이

그리디 알고리즘 문제이다. 가지고 있는 동전의 가치를 임의의 배열에 집어넣고 if 절을 사용하여 필요한 동전의 개수를 계산함과 동시에 총 계산할 값을 나머지로 갱신하는 방법으로 풀 수 있다.

가치가 큰것에서 시작하여 작은것 순으로 계산해줘야 간단하게 작성할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int a[11]; 
int n, k;

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i]; //동전의 가치 배열에 집어넣기
	}
	int sum = 0;
	for (int j = n-1; j >= 0; j--) { //배열은 a[0]에서 시작, a[n-1]이 끝
		if (a[j] <= k) {
			sum = sum + k / a[j]; //동전 개수 더하기
			k = k % a[j]; //총 계산할 값은 위 식을 수행한 나머지
		}
	}
	cout << sum;
}