BOJ 백준온라인져지 11047 동전 0 풀이

Greedy Algorithm은 그 상황에 따라 그 상황이 최적이라고 가정하고, 최적해를 구하는 방법이다.

결론적으로는 해답에 도달한다.

하지만 그 선택들을 수집해서 최종적인 답이 최적이라는 보장이 없다.

Greedy Algorithm은 대부분 두 가지 조건이 만족된다.

1. 탐욕스런 선택 조건(Greedy Choice Proerty): 앞의 선택이 뒤에 영향을 주지 않는다.
2. 최적 부분 구조 조건(Optimal Substructure): 문제에 대한 최적해가 부분문제에 대해서도 최적해다.

문제로 돌아오면,

 K를 만드는 최소의 Ai 개수를 구하는 것이다.

풀이 방법은

오름차순으로 정렬된 동전의 가치를 저장한다.

내림차순으로 동전과 K의 가치를 비교한다. 동전의 가치가 더 크다면 그 동전은 사용하지 않고,

다음 동전으로 넘어간다.

K 가치가 더 큰게 나오면 K -= (K / Ai) * Ai를 해준다.

몇개를 사용하는지 체크해주기 위해 result += (K / Ai)를 해준다.

	#include <cstdio>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/11047
	* BOJ 백준온라인져지 11047 동전 0 풀이
	*/
	using namespace std;
	int main(){
	int N, K;
	scanf("%d%d", &N, &K);
	int loopCount = N;
	vector<int> value;
	while(loopCount--){
	int tempValue;
	scanf("%d", &tempValue);
	value.push_back(tempValue);
	}
	int result = 0, idx = value.size() - 1;
	while(K){
	while(K < value[idx]){
	idx--;
	}
	result += K / value[idx];
	K -= value[idx] * (K / value[idx]);
	}
	printf("%d", result);
	}

view raw BOJ_11047.cpp hosted with ❤ by GitHub