시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (하단 참고)512 MB3001118944.059%

문제

아름이는 주사위 N개를 가지고 있다. 주사위는 정육면체 모양이고, 크기는 N개 모두 동일하다. 일반적인 주사위와 다르게, 여섯 개의 면에는 정수가 하나씩 쓰여 있다. 한 주사위에는 모두 같은 정수가 쓰여 있다.

주사위 탑이란 주사위를 위로 쌓은 모양을 의미한다. 주사위를 쌓을 때는 주사위의 변이 일치하게 쌓아야 한다. 주사위 N개를 쌓아서, 주사위 탑의 개수를 최소로 하려고 한다.

주사위에 쓰여 있는 수를 s라고 했을 때, 그 주사위의 위에는 최대 s개의 주사위를 올려놓을 수 있다.

예를 들어, 주사위가 총 4개 있고, 각 주사위에 쓰여 있는 수가 1, 2, 4, 5인 경우를 생각해보자. 주사위를 쌓은 결과가 위에서부터 2, 1, 4, 5인 경우는 가능하다. 2가 적힌 주사위 위에 0개, 1이 적힌 주사위 위에 1개, 4가 적힌 주사위 위에 2개, 5가 적힌 주사위 위에 3개가 있기 때문이다. 하지만, 4, 1, 5, 2의 순서로 쌓는 것은 불가능하다. 2가 적힌 주사위의 위에 주사위가 총 3개 있기 때문이다.

주사위의 개수 N과 각 주사위에 쓰여 있는 수가 주어졌을 때, 만들 수 있는 주사위 탑의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 주사위의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 주사위에 쓰여 있는 수가 주어진다. 주사위에 쓰여 있는 수는 1,000보다 작거나 같은 양의 정수 또는 0이며, 공백으로 구분되어져 있다.

출력

첫째 줄에 만들 수 있는 주사위 탑의 최소 개수를 출력한다.

예제 입력 1

4
1 2 4 5

예제 출력 1

1

예제 입력 2

4
1 2 1 2

예제 출력 2

2

예제 입력 3

5
0 0 0 0 0

예제 출력 3

5

힌트

아래 설명에서 k개의 주사위가 쌓여져 있고, 위에서부터 적혀있는 정수가 s1, s2, ..., sk인 주사위 탑을 (s1, s2, ..., sk)로 표현했다.

예제 1의 경우에는 주사위 탑 1개를 만들 수 있다. (1, 2, 4, 5) 또는 (2, 1, 4, 5)와 같이 주사위 탑 1개를 만들 수 있으며, 다른 방법도 존재한다.

예제 2의 경우에는 2개보다 작은 주사위 탑을 만들 수 없다. (1, 2), (1, 2)로 2개를 만들 수 있다. (1, 1, 2), (2)와 같은 방법도 가능하다.

예제 3의 모든 주사위에 적혀있는 정수는 0이다. 따라서, 한 주사위 위에 다른 주사위를 쌓을 수 없다. 따라서, 모든 주사위 탑은 주사위 1개로 이루어져 있다.

출처

  • 문제의 오타를 찾은 사람: jh05013

시간 제한

  • Python 3: 12 초
  • PyPy3: 12 초
  • Python 2: 12 초
  • PyPy2: 12 초

채점 및 기타 정보

  • 예제는 채점하지 않는다.