문제

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’ 측정을 한다. ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어져서, 공포도가 X인 모험과는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정하였다. 최대 몇개의 모험가 그룹을 만들 수 있을지 알아보자.

예를 들어서 N = 5이고, 각 모험가의 공포도가 다음과 같다고 가정하자.

2 3 1 2 2

이 때, 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두명을 넣게 되면, 총 2개의 그룹을 만들 수 있다. 또한 몇 명의 모험가는 마을에 남아 있어도 되어, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.

입력 조건

• 첫째 줄에 모험가의 수 N이 주어진다 (1 ≤ N ≤ 100000)
• 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분

출력 조건

• 여행을 떠날 수 있는 그룹 수의 최대값을 출력

코드(틀)

회고

우선 문제의 조건을 보고 공포도가 낮은 사람들로 최대한 많은 팀들을 만들어야 한다고 생각했다. 그래서 그 순서대로 하기 위해서, 정렬을 한다는 아이디어 까지는 좋았고 이미 결성된 팀에 누군가를 더 넣는것이 의미가 없다 생각하였던 것도 좋았다. 다만, 아래와 같은 경우를 생각 못한것이 패착이었다.

3 3 4 4

내 코드는, 모지리와 더 모지리가 그래도 힘을 합쳐서 요구 사항을 만족시킨다 라는 것을 생각을 못했다… 그래도 정렬이라는 것을 생각해냈다는 것에 의의를 둬야할까… 갈 길이 멀다. ‘하’ 난이도를 시원하게 틀려먹었지만, 그래도 쎈 수학 공부법은 이어져야 할 테니… 앞으로는 TC를 두개정도 더 만들고, 문제의 코드로 답을 만들지 말고, ‘인간의 방법’으로 만든 답과 비교해야지…