동전 0 (feat. 백준, 11047번)

동전 0
https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, K, ans = 0, arr[10];
	cin >> N >> K;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i];
	for (register int i = N - 1; i >= 0; --i) {
		ans += K / arr[i];
		if ((K = K % arr[i]) == 0)
			break;
	}
	cout << ans;
	return 0;
}
// *&)*@**

1. 큰 동전부터 주어진 K에 대해서 나눴을때, 만약 몫이 있다면 몫만큼 해당 동전을 사용했다는 의미일 것입니다.
2. 즉, 4500원은 5000원으로 나눴을때 몫은 0 이지만 1000원으로 나눴을때 몫은 4 입니다. 따라서 1000원을 4개 사용했고 나머지 2500원에 대해서 다음 동전으로 나누어주면 되겠습니다.