크기가 4인 박스

면접 대비

시간 제한1초메모리 제한1024 MB

요약

크기가 1에서 4인 물건들과 용량 4인 박스가 주어질 때, 모든 물건을 담는 최소 박스 개수를 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

탐욕스러운 동건이는 $N$ 개의 물건을 훔쳤고, 이제 모든 물건들을 크기가 $4$ 인 박스들에 나누어 담아야 한다. 각 물건의 크기는 $1$ 이상 $4$ 이하의 정수이며, 하나의 박스에는 크기의 합이 $4$ 를 넘지 않도록 여러 물건을 넣을 수 있다. 동건이가 모든 물건을 담기 위해 필요한 박스의 최소 개수를 구하여라.

입력

첫째 줄에 물건의 개수를 나타내는 정수 $N$ 이 주어진다. $(1 \le N \le 100\\,000)$

둘째 줄에는 각 물건의 크기를 나타내는 $N$ 개의 정수 $a\_i$ 가 주어진다. $(1 \le a\_i \le 4)$

출력

동건이가 모든 물건을 담기 위해 필요한 박스의 최소 개수를 출력한다.

예제1

예제 1
입력
```
4
1 2 3 4
```
예상 출력
```
3
```