Greedy

그 순간에 최적이라고 생각되는 것을 선택해나가며 답을 구하는 방식. 왜 이 답이 정답인지 증명할 수 있어야 한다!

Codeforces 734B: Anton and Digits

문제

2, 3, 5, 6들을 가지고 256과 32의 합을 최대한 크게 만드는 문제. 256과 32는 2가 겹치기 때문에 2만 고려해주면 된다. 먼저 2, 5, 6 중 개수가 가장 적은 수만큼 256을 만든 다음, 남은 2와 3들로 32를 만들면 된다.

greedy 문제를 풀 때는 정답인지 확인하는 과정이 필요하다.

greedy한 방법으로 풀지 않았다고 해보자. 여기서는 256을 greedy로 풀 때 보다 적게 만드는 방법이 있다. 그러나 이러한 방식으로 풀 때 정답보다 (256 - 32)x(덜 만든 256의 개수)만큼 전체 합이 작아지므로, 정답이 아니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int two, three, five, six;
	long long cnt1, cnt2; // cnt1: 256, cnt2: 32
	cin >> two >> three >> five >> six;

	int tmp1 = min(min(two, five), six);
	cnt1 = (tmp1 * 256);
	two -= tmp1;

	int tmp2 = min(two, three);
	cnt2 = (tmp2 * 32);

	cout << cnt1 + cnt2 << endl;
	return 0;
}

Codeforces 158B: Taxi

문제

1, 2, 3, 4명의 그룹이 있고 택시에는 최대 네 명의 승객이 탈 수 있으며 모든 그룹 멤버들끼리는 같은 택시에 탑승해야 할 때, 택시를 최소 몇 번 몰아야 하는지 구하는 문제.

승객을 최대한 꽉꽉 채워넣어야 한다. 먼저 4인 그룹은 택시 한 대를 다 차지하므로 4인 그룹의 수만큼 cnt에 더한다.
그 다음 3인 그룹을 처리한다. 이때 한 자리가 비므로 1인 그룹을 최대한 채운다.
그 다음 2인 그룹을 처리한다. 두 2인 그룹끼리는 택시를 공유할 수 있으므로 짝수 개의 2인 그룹들을 같이 태운다.
마지막으로 남는 2인 그룹과 1인 그룹들을 처리한다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, one, two, three, four, cnt, tmp;
	one = two = three = four = cnt = 0;
	cin >> N;

	while (N--) {
		cin >> tmp;
		switch (tmp) {
		case 1: one++; break;
		case 2: two++; break;
		case 3: three++; break;
		case 4: four++; break;
		default: break;
		}
	}

	// groups of 4
	cnt += four;

	// groups of 3
	cnt += three;
	if (one > three) one -= three;
	else one = 0;

	// groups of 2
	cnt += (two / 2);
	two %= 2;

	// groups of 2 and 1
	if (two > 0) {
		cnt++;
		one -= 2;
	}
	if (one > 0) {
		cnt += (one / 4);
		one %= 4;
		if (one > 0) cnt++;
	}

	cout << cnt << endl;
	return 0;
}

Codeforces 160A: Twins

문제

전체 합의 절반보다는 무조건 많으면서 동전의 수는 최소가 되도록 가져갈 때, 가져가는 동전의 수를 구하는 문제. 절반 초과 ~ 절반 + 10 이하 같은 문제가 아니라 절반보다 많기만 하면 되기 때문에, 동전의 값들을 내림차순으로 정렬한 다음에 절반보다 커질 때까지 가져가면서 cnt를 증가시키면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // std::greater
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, total, sum, cnt, i, tmp;
	vector<int> v;

	cin >> N;
	total = sum = cnt = 0;

	for (i = 0; i < N; i++) {
		cin >> tmp;
		v.push_back(tmp);
		total += tmp;
	}

	total = total / 2;

	sort(v.begin(), v.end(), greater<int>());

	for (i = 0; i < N; i++) {
		sum += v[i];
		cnt++;
		if (sum > total) break;
	}

	cout << cnt << endl;
	return 0;
}