BOJ 11047 동전 0

가장 기본적인 그리디를 연습할 수 있는 문제이다. 조금더 실전과 같은 훈련을 하기 위해 타이머를 설정하고 문제를 풀었다. 비교적 쉬운 난이도여서 약 8분정도 만에 문제를 해결하였다.

 

풀이방법은 N개의 동전을 가치가 가장 큰 순서대로 정렬을 한다. 그리디는  말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 따라서 동전 개수를 최소한으로 하기 위해 선택의 순간마다 가치의 합 K를 결정할때 K보다 작은 동전중 가장 큰 가치를 가진 동전을 선택하면 된다.

 

예를들어 예시가 다음과 같이 주어졌을경우

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 4200원 보다 작은 동전 중 가치가 가장 큰 1000을 고르면 된다. 이후 1000을 골랐기 때문에 다은 선택의 순간은 3200원이 된다. 선택의 순간이 0 이될때까지 반복하다. -> 3200 - 2200 - 1200 - 200 - 100 - 100

 

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

bool cmp(int a,int b)
{
	return a > b;
}

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

	vector<int> v;
	int n, k;
	cin >> n >> k;

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

	sort(v.begin(),v.end(), cmp);

	int cnt = 0;
	for(int i = 0; i < v.size(); i++)
	{
		if(k == 0)
		{
			break;
		}
		if(v[i] > k)
		{
			continue;
		}
		k -= v[i];
		cnt++;
		i--;
	}

	cout << cnt;
}