B11047

개요

백준 문제 11047번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 20분
https://www.acmicpc.net/problem/11047

문제

동전을 적절히 사용해서 주어진 가치 K를 만들어야함

코드

#include <iostream>

using namespace std;

const int MAX = 10;
int coinVal[MAX];
int N;
int objVal;
void greedy()
{
	int sum = 0;
	int valIdx = N-1;
	int countAddCoin = 0;
	while(objVal != sum)
	{
		if(sum + coinVal[valIdx] > objVal)
		{
			valIdx--;
		}
		else
		{
			sum += coinVal[valIdx];
			countAddCoin++;
		}
	}	
	cout << countAddCoin;
}


void solve()
{
	cin >> N >> objVal; 
	for(int i=0;i<N;i++)
	{
		cin >> coinVal[i];
	}
	greedy();
}	


int main()
{

	solve();
}

풀이

항상 1원짜리가 들어와서 걱정없이 그리디를 적용할 수 있음.
K를 넘지않는 제일 큰 동전을 추가하면 해결

배울 점, 메모