뚝딱뚝딱

그리디 알고리즘의 대표적인 예시 중 하나인 동전 문제를 풀어보자.

다음과 같은 절차로 해결할 수 있다.

1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택 한다.
2. 적절성 검사 : 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택한다.
3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결된 것이다.

+여기에 부가적인 절차는 주석으로 작성하였다.

#include<iostream>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;

	int *a = new int[N];

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

	int cnt = 0; //동전의 개수를 저장할 것이다

	for (int i = N - 1; i >= 0; i--) {//문제에서 동전의 가치를 오름차순으로 저장했으므로,뒤에서부터 비교한다
		if (a[i] <= K) {//입력받은 가치보다 작은 것중 가장 큰 걸 선택
			cnt += (K / a[i]);//큰 가치로 몇번 나누어질 수 있는지를 구하고 더한다
			K = K % a[i];//그 나머지를 K로 갱신한다
		}
	}

	cout << cnt;//최종 cnt를 출력한다
}