11047번 : 동전 0

문제는 다음과 같습니다.

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

11047번: 동전 0

 

풀이 코드는 다음과 같습니다.

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	int n,m;
	vector<int>v;
	cin>>n>>m;
	for(int i{0};i<n;i++)
	{
		int temp;
		cin>>temp;
		v.push_back(temp);
	}
	int count{0};
	for(int i{v.size()-1};i>=0;i--)
	{
		if(m==0)
		{
			break;
		}
		else
		{
			while(m>=v[i])
			{
				count++;
				m-=v[i];
			}
		}
	}
	cout<<count<<endl;
	return 0;
}

동전의 개수를 최소로 하기 위해 가장 큰 수부터 확인합니다.

문제에서 입력 때 부터 오름차순으로 입력하기 때문에 정렬하는 과정이 따로 필요하지 않습니다.

이후 적당한 동전 가치를 찾으면 동전을 하나 증가 시킴과 동시에 입력받은 값에 동전 가치를 차감하는 과정을 반복하여 동전이 얼마나 필요한지 확인할 수 있습니다.