팀 timer 6s memory 256MB

곧 다가올 한컴 알고리즘 대회를 준비하던 택쌤은 n명의 학생들의 최종 접수를 확인했다. 택쌤이 이번 대회는 팀 단위로 개최했기 때문에, n명의 참가자들은 여러 팀으로 분류되게 된다. 열심히 대회를 준비하던 택쌤은 어느 날 밤 잠을 자다가, 대학 시절을 회상하는 꿈을 꾸게 되었다.

택쌤의 대학교 시절에도 팀 단위로 하는 알고리즘 대회가 있었다. 그런데 한 팀에서 한 명만 너무 월등히 똑똑하고, 나머지 세 명은 그 한 명의 설명을 이해하지 못해서 결국 팀워크가 맞지 않아 망한 팀이 있었다. 헉. 택쌤은 확 잠에서 깼다. 그리고 깨달았다. “팀원들끼리 실력 차이의 갭이 너무 크면, 오히려 결과에 악영향을 끼치고 개인전보다도 성적이 안 나온다!”

다행히도 택쌤은 n명의 참가자들의 실력을 알고 있으며, 정수(소수점이 없는 수)의 형태로 수치화 시켜 놨다. 물론 여러분들처럼 버그가 가득한 코딩을 전문적으로 해서 팀에 악영향을 끼치거나, 설명을 해줘도 이해를 잘 못하기 때문에 오히려 시간을 더 잡아먹는 학생들도 있기 때문에, 음수의 실력을 가진 학생도 있다. 팀워크가 맞기 위해서는, 팀원들의 실력이 연속적이어야 한다. {5,6,7,8} 이나 {-3,-2,-1,0,1,2} 또는 {3} 처럼 말이다. 그래야 8의 실력을 가진 학생이 7에게 설명해주고, 6에게 설명해주고, 5에게 설명해주고 5가 이해하고…… 이런 식으로 팀워크를 이뤄나갈 수 있다. 그런데 까다로운 택쌤은 같은 실력을 가진 학생들끼리는 같은 팀이 안되게 하고 싶다. 즉 {4,4,5,6,7} 같은 팀은 조건 위배이다.

그래도 팀 단위 대회이기 때문에 한 팀안에 팀원들이 많은 게 재밌을 것이다. 위 조건을 만족하면서 학생들을 여러 팀으로 분류했을 때, 가장 적은 팀원 수를 최대화시키는 프로그램을 작성하라.

예를 들어 n이 6이고, 참가자들의 실력이 {-1,0,1,2,2,3} 이라고 하자. 팀을 나누는 방식은 여러 가지가 있다: {-1}{0}{1}{2}{2}{3} 이나 {-1,0,1,2,3}{2}, 또는 {-1,0,1,2}{2,3} 같은 경우가 있다. 첫번째나 두번째의 경우 가장 적은 팀원 수가 1명이지만, 세번째 경우는 {2,3} 팀의 2명이고, 그것보다 나은 분류 방법이 없으므로 이 경우의 답은 2이다. {-1,0,1}{2,2,3} 은 {2,2,3} 에 동실력자가 있으므로 조건 위배, {-1,0,2}{1,2,3} 은 {-1,0,2} 가 연속된 수가 아니므로 조건 위배이다. 주의: 대회이기 때문에, 0명의 참가자들이 입력으로 주어질 수도 있다. 당연히 이 경우의 답은 0이다(최대 0명짜리 팀 밖에 못 만들기 때문에).