| 동아리 회식 |
|---|
충북과학고에는 N개의 동아리가 있다. 학생들은 중간 고사가 끝나자 동아리별 친목 도모를 위해 시내에서 동아리별 회식을 하기로 계획하고 학교로 콜 택시를 부르려고 한다. \(i\) 동아리는 \(S_i(1 \leq S_i \leq 4 )\) 인원으로 구성되어 있다. 한 동아리의 모든 부원들이 한 택시에 탑승하려고 할 때 전체 동아리가 시내에 가기 위해 불러야 할 콜 택시의 최소 대수를 구하는 프로그램을 작성하시오. 한 택시에 하나 이상의 동아리가 탑승할 수 있으며, 한 택시에는 최대 4명까지 탑승할 수 있다. |
| 입력 | |
|---|---|
첫째 줄에 동아리 수 \(N(1 \leq N \le125)\)이 주어진다. 두 번째 줄에 각 동아리의 인원이 정수열 \(s_1, s_2, ... , s_n (1 \leq s_i \leq 4)\)이 공백을 사이에 두고 주어진다. | |
| 출력 | |
|---|---|
첫째 줄에 전체 동아리가 시내에 가기 위해 불러야 할 콜 택시의 최소 대수를 출력한다. 예시1에서 다음과 같이 택시에 탈 수 있으며, 택시에 타는 방법은 다양할 수 있다. (하나의 괄호가 하나의 택시다) (3동아리), (4동아리), (5동아리), (1동아리 2동아리) | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 5 1 2 4 3 3 | |
| 출력 | 4 | ||
| 2 | 입력 | 8 2 3 4 4 2 1 3 1 | |
| 출력 | 5 | ||