백준 C++ | #18 BOJ11047 동전 0 C++ 문제 풀이

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

 

그리디 알고리즘 예제로 푼 문제다. 

그리디 알고리즘에서 가장 유명한 잔돈 문제의 입출력 형태를 살짝 바꾼 문제였다. 

그리디 알고리즘은 제일 간단한 것이라 그런가, 

알고리즘의 실체가 뭔지를 모르겠다. 

이 문제들은 '걍 푼다' 아닌가..? 

 

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int n, k;
	std::cin >> n >> k;
	std::vector<int> v;

	for (int i = 0; i < n; i++) {
		int tmp;
		std::cin >> tmp;
		v.push_back(tmp);
	}
	std::reverse(v.begin(), v.end());

	int count = 0;
	for (int i = 0; i < n; i++) {
		count += k / v[i];
		k = k % v[i];
	}

	std::cout << count << std::endl;
}

 

아래 블로그에서 그리디 알고리즘의 문제 추천을 받았다. 

Greedy Algorithm (그리디 알고리즘, 탐욕법) 개념 정리 & 문제 추천 — HELLO RUNA! (tistory.com)