코테/Greedy
[C/C++] 나동빈 모험가 길드, Greedy
상똥
2023. 2. 6. 15:48
문제
한 마을의 모험가가 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동안 반복한다.