메뉴 건너뛰기

문제

00c02 동아리 회식 1  

시간메모리제출 올바른 답 비율
1초64MB
496
44
8.9%


나의 횟수나의 최근 판정시도 성공 비율
6535
53.8%
동아리 회식  

충북과학고에는 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
위로