[greedy / c++] 최대의 모험단 수 만들기

그리디 관련 공부가 필요해서 아래 유튜브의 그리디 영상을 보고 이해하는데 시간이 좀 걸렸던 문제를

코드로 하나하나 이해해가며 따라해보았다

생각보다 문제가 이해하기 난해했다. 코드 옆에 주석에 문제와 이해한 해석을 달아보았다

https://www.youtube.com/watch?v=2zjoKjt97vQ 

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> arr;

// 모험가 길드 문제  


// n명의 모험가가 있다. 공포도가 x명인 모험가는 x명 이상의 모험단에
// 참여해야만 출발이 가능하다. 최대로 떠날 수 있는 모험단의 수는?

// 모험가가 모험단에 모두 속할 필요는 없다. 


int main(){
	// 공포도가 작은 수부터 모험단을 만들어야
	// 최대의 모험단 수를 얻을 수 있다  
	
	cin >> n; // n명의 모험가 
	for(int i=0; i<n; i++){
		int x;  // x의 공포도 
		cin >> x;
		arr.push_back(x); // 공포도의 벡터 만들기 
	}
	
	sort(arr.begin(), arr.end());
	int result=0; // 모험단의 수 
	int cnt=0; // 현재 모험단의 모험가의 수 
	for(int i=0; i<n; i++){
		cnt++; // 모험가를 센다
		if(cnt>=arr[i]){  // 오름차순이므로 현재 센 모험가 수가 현재
						  // 공포도 이상을 가지면 모험단++, cnt 초기화
			result++; // 혹은 result += 1 
			cnt=0; 
		}
	}
	cout << result << "\n"; 
	
	return 0;
}