백준 11047 _ 동전 0

www.acmicpc.net/problem/11047

11047번: 동전 0

---

✨ 내 소스 코드

#include<iostream>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K,result=0;
	cin >> N >> K;

	vector<int> coin;

	while (N--) {
		int temp;
		cin>>temp;
		coin.push_back(temp);
	}

	for (int i = coin.size() - 1; i >= 0; i--) {
		if (coin[i] <= K) {
			result = result + (K / coin[i]);
			K = K % coin[i];
		}
		if (K <= 0) break;
	}
	cout << result;
	system("PAUSE");

	return 0;
}	

 

🙏 문제 풀이

처음엔 이분탐색을 이용해서 풀었으나, 시간 초과로 실패하였다

이후에 다시 생각을 해보니 모든 동전을 한번만 탐색하여 풀 수 있는 문제였다

 

K보다 작지만 가장 큰 동전으로 나누고 남은 K는

어찌되었든 이전에 나누었던 동전보다 작은 값의 동전으로 나누게 된다

이분탐색으로 계속해서 가장 근접한 동전을 찾을 필요 자체가 없었다

 

⭐ 문제 풀이 결과