시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 75 15 14 38.889%

문제

서울 관악구 신림동에 살고 있는 성지의 생일이 3일 앞으로 다가왔다. (황성지 아닙니다!) 일요일에서 월요일이 되는 12시 정각, 902호에서 자음 퀴즈의 달인 성지의 생일을 기념하는 성대한 파티가 열릴 예정이다. N명의 학생이 참석하기를 원하며, 넘을 수 없는 4차원 세계에 살고 있는 성지는 물론 참석한다.

모든 학생은 자신이 파티에 초대될 것이라 굳게 믿고 있으며, 자신과 순수한 소년 성지를 제외하고 적어도 k명의 학생은 참석해야 한다고 굳게 믿고 있다.

생일빵을 두려워하기 때문일까? 띄어쓰기를 잘 못하는 성지는 가능하면 학생들을 적게 초대하고 싶다는 의사를 밝혔다. 하지만 사려깊은 성지는 학생들의 생각 (자신과 성지를 제외하고 적어도 k명의 학생은 참석해야 한다는) 을 모두 만족시키기를 원한다.

학생의 수 N과 각 학생들이 생각하는 k값이 모두 주어졌을 때, 학생들의 생각을 모두 만족시키면서 초대할 수 있는 최소의 학생 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 N이 주어진다. (1≤N≤10,000) 이어서 N개 줄에 걸쳐 각 학생이 생각하는 k 값이 주어진다.

출력

첫째 줄에 학생들을 만족시키면서 초대할 수 있는 최소 학생 수를 출력한다.

예제 입력

2
1
1

예제 출력

2

힌트

한 명만을 초대할 수는 없다. 모두가 자신과 성지를 제외하고 적어도 한 명의 학생은 참석해야 한다고 믿고 있기 때문에… 따라서 두 명 모두 초대해야 한다.

출처

  • 문제를 번역한 사람: author5