백준 BOJ 11047 - 동전 0

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

11047번: 동전 0

Ai는 Ai-1의 배수라는 조건덕분에 그리디알고리즘으로 해결 가능한 문제이다.

Ai-1번째 k개를 선택해서 값을 채우느니 그냥 k배인 Ai를 사용하면

동전 수를 절약할 수 있기때문에

(100원 다섯개 vs 500원 한개의 차이)

​

가장 큰 동전부터 계산해서 지불해야하는 금액을 줄여나가면 된다.

#include <stdio.h>

int main(){
	int n,k,sum=0;
	int arr[11] = {0};
	scanf("%d %d", &n, &k);
	for(int i=1; i<=n; i++){
		scanf("%d", &arr[i]);
	}
	for(int i=n; i>=1; i--){
		while(arr[i] <= k){
			k -= arr[i];
			sum++;
		}
	}
	printf("%d", sum);
}