[C/C++ 백준 11047번] 동전 0 (Silver 1)

www.acmicpc.net/problem/11047

11047번: 동전 0

각 코인의 가치가 이전 코인의 가치의 배수이기 때문에, 최대한 큰 코인을 쓰는 것이 무조건 이득이다. 큰 코인부터 써가면서 동전 개수를 카운트 해주자.

 

#include <cstdio>
int main(void){
	int coin[11], ans=0;
	long long int N, K;
	scanf("%lld %lld", &N, &K);
	for(int i=0; i<N; i++){
		scanf("%d", &coin[i]);
	}
	int cnt = N-1;
	while(K){
		ans += K/coin[cnt];
		K -= coin[cnt]*(K/coin[cnt]);
		cnt--;
	}
	printf("%d",  ans);
}