[C++] 백준 11047 동전 - 탐욕

처음에는 막연히 동전을 큰 순서대로 넣어야지라는 생각으로 코드를 이렇게 짰다.

그랬더니 시간이 212ms나 걸렸다.

코드↓

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


vector<int> coin;
vector<int> countCoin;
int n;
int k;
int sumCoin = 0;

void Coin();

int main()
{
	ios::sync_with_stdio(false);

	cin >> n >> k;

	int input;
	for (int i = 0; i < n; i++)
	{
		cin >> input;
		coin.push_back(input);
		countCoin.push_back(0);
	}

	sort(coin.rbegin(), coin.rend());

	Coin();

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		result += countCoin[i];
	}

	cout << result;

	return 0;
}


void Coin()
{
	for (int i = 0; i < n; i++)
	{
		while (1)
		{
			if (sumCoin + coin[i] <= k)
			{
				sumCoin += coin[i];
				countCoin[i]++;
			}
			else
			{
				break;
			}
		}
		if (sumCoin == k) break;
	}
}

 

하지만 생각해보니 너무 비효율적이였다. 그렇게 다시 생각해보니 굳이 값을 다시 계산할 필요가 없었다.

걸린 시간이 신기하게 0ms이였다.

코드↓

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

int main()
{
	ios::sync_with_stdio(false);

	vector<int> coin;
	int n;
	int k;
	int input;
	int result = 0;

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		coin.push_back(input);
	}

	for (int i = n; i > 0; i--)
	{
		result += k / coin[i - 1];	//가치의 합 k를 가장 높은 코인의 값부터 나누어 개수를 적립.
		k %= coin[i - 1];	//가장 높은 코인의 값을 나눈 나머지를 다음 차수에 나눈다.
	}

	cout << result;

	return 0;
}

 

풀이

- 큰 값을 차례대로 값을 나눈 값이 코인의 개수이므로 그만큼의 개수를 적립한다.

- 남은 값은 나머지를 활용하여 다시 나눠주어 남은 값에서 다음 큰 값을 나눈다.