백준 알고리즘 문제 풀이 c/c++ -11047-

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

• 그리디 알고리즘
• 주어진 동전들이 모두 배수 관계에 있으므로 가능
• 가장 가치가 높은 동전부터 최대한 사용한다

#include <stdio.h>
#include <algorithm>

using namespace std;


int n; // 동전 개수
int K; // 동전을 최소로 사용해서 그 합을 K로 만들어야 한다

int Count = 0; // 사용 동전 개수 누적 합

int arr[10];  // 동전 담을 배열

int main() {

	scanf("%d %d", &n, &K);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	for (int i = n - 1; n >= 0; i--) {
	
		Count += K / arr[i];
		
		if (K % arr[i] == 0)
			break;
		
		K = K % arr[i];
	}

	printf("%d\n", Count);


	return 0;
}