[BOJ] 11047 | 동전 0

문제

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

풀이

문제를 읽어보면, “A_1 = 1, i ≥ 2인 경우에 A_i는 A_{i-1}의 배수”라는 조건이 있는데,

첫번째 조건을 통해, “만들지 못하는 경우는 없다.”를 추측해낼 수 있고,

두번째 조건을 통해, “tA_{i-1}는 A_i로 대체할 수 있다.”를 추측해낼 수 있다. (t는 임의의 상수)

가치가 A_i인 동전을 가치가 A_{i-1}동전으로 대체할 수 있으나,

가치가 A_{i-1}를 여러개 쓰는 것 보다, 가치가 A_i인 큰 동전 하나로 바꾸는게 이득이라는 것을 알 수 있다.

이렇게 가장 큰 동전부터 사용하여, greedy한 방법으로 정답을 찾을 수 있다.

시간복잡도는 동전의 개수, 즉 O(N)이다.

소스

#include<iostream>
using namespace std;

int n, k, cnt, coin[11];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <=n; i++)
		cin >> coin[i];
	while (n) {
		if (coin[n] > k) {
			n--;
			continue;
		}
		cnt += k / coin[n];
		k %= coin[n];
	}
	cout << cnt;
}