페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2616

[초등부] 2025 KOI 2차대회 대비 모의고사 (1회차)

색깔 토끼
서브태스크
1초 1024MB

문제

스티비라는 고양이가 토끼 마을을 방문해, 몇 마리의 토끼에게 다음과 같은 질문을 했다.

“네 자신을 제외하고, 너와 같은 색의 토끼가 총 몇 마리나 살고 있니?”

물어본 토끼들은 모두 한 번만 질문을 받고 진실만 말했다.

예를 들어 검은색 토끼가 세 마리 있고, 분홍색 토끼가 두 마리 있는데, 그 중 분홍색 토끼 두 마리와 검은색 토끼 두 마리에게 스티비가 질문을 한다면 아래와 같은 답이 나올 것이다.

분홍색 토끼 A: "나를 제외하고 같은 색 토끼가 총 1 마리 있어."

분홍색 토끼 B: "나를 제외하고 같은 색 토끼가 총 1 마리 있어."

검은색 토끼 C: "나를 제외하고 같은 색 토끼가 총 2 마리 있어."

검은색 토끼 D: "나를 제외하고 같은 색 토끼가 총 2 마리 있어."

이 상황에서 스티비가 파악할 수 있는 총 토끼의 수는 검은색 세 마리, 분홍색 두 마리로 총 다섯 마리다.


스티비는 이 답을 바탕으로 이 마을에 최소 몇 마리의 토끼가 살고 있는지 알고 싶다.


입력

첫째 줄에 스티비가 질문한 토끼의 수 N이 주어진다.

다음 N개 줄에, 각 토끼가 대답한 정수 a_i가 한 줄에 하나씩 주어지는데, a_i는 "자신을 제외한 같은 색 토끼 수"를 의미한다.

제한

  • 1 ≤ N ≤ 50

  • 0 ≤ a_i ≤ 1 000 000


출력

토끼 마을에 최소 몇 마리의 토끼가 살고 있는지 한 줄에 출력한다.


부분문제

번호 점수 조건
#110점

a_i = 0 (1 \le i \le N)

#220점

a_i \le 1 (1 \le i \le N)

#330점

N \le 5

#440점

추가 제약 조건 없음


예제 #1

4
1
1
2
2
5

예제 #2

1
0
1

예제 #3

9
2
2
44
2
2
2
444
2
2
499
로그인해야 코드를 작성할 수 있어요.