[백준] 단계별로 풀어보기 > 그리디 알고리즘 (c++)

문제 1. 동전 0

• 가장 금액이 큰 동전부터 개수를 세면서 k원에서 차감해줌
• k가 0이되면 동전의 개수를 출력 

#include <iostream>
#include <map> 

using namespace std;

int main() {
	int n, k, tmp;
	map<int, int> m;
	map<int, int>::reverse_iterator reiter;

	cin >> n >> k;
	
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		m[tmp] = 0;
	}

	for(reiter = m.rbegin(); reiter != m.rend(); reiter++) {
		while (reiter->first <= k) {
			m[reiter->first]++;
			k -= reiter->first;
		}

		if (k <= 0) break;
	}

	tmp = 0;
	for (reiter = m.rbegin(); reiter != m.rend(); reiter++) {
		if (reiter->second > 0) {
			tmp += reiter->second;
		}
	}

	cout << tmp << "\n";
    
    return 0;
}

 

문제 2. 회의실 배정

 

 

문제 3. ATM

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

using namespace std;

int main() {
	int test_case;
	int a, sum=0;
	
	vector<int> v;

	cin >> test_case;

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

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

	for (int i = 0; i < test_case; i++) {
		for (int j = 0; j <= i; j++) {
			sum += v[j];
		}
	}

	cout << sum << "\n";
    
    return 0;
}

 

문제 4. 잃어버린 괄호

 

 

문제 5. 주유소

 

 

결과