[C/C++] 나동빈 모험가 길드, Greedy

문제

한 마을의 모험가가 N명이고, 각 모험가의 공포도는 X이다. 공포도가 X수준인 모험가는 반드시 X명 이상의 모험가 길드에 참여해야 모험을 떠날 수 있다. 모험을 떠나지 않고 마을에 남아있을 수 있으므로 모든 모험가가 길드에 가입해야 하는 것은 아니다. 공포도는 모험가의 수보다 작거나 같다. 모험을 떠날 수 있는 그룹의 최대 수를 구하라. 예를 들어 5명의 모험가가 있다고 할 때 각각의 공포도가 2 3 1 2 2 라면, 모험을 떠날 수 있는 그룹은 2팀이다. 첫 번째줄에 모험가의 수가 주어지고 두 번째 줄에 공포도가 주어진다.

코드

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main() {
	vector<int> X;
	int N, x, num = 0, index = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x;
		X.push_back(x);
	}

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

	x = 1;
	while (index < N) {
		if (X[index] == x) {
			num++;
			x = 1;
		}
		else if (X[index] > x)
			x++;
		index++;
	}
	cout << num;
}

풀이

1. X를 오름차순으로 정렬한 후, 기본 공포도 x를 1로 초기화한다. 모험가의 공포도 X를 순서대로 읽을 index 변수를 선언한다.

2. X의 원소를 index에 따라 기본 공포도 x=1과 비교한다.

3. X[index] == x라면, index와 모험을 떠날 수 있는 총 그룹의 수 num을 하나 증가시킨다.

4. X[index] > x라면, index와 x를 하나씩 증가시킨다.

5. 2~4번 과정을 index<N동안 반복한다.