Informatica Online Judge

  포장 [0751 / 02EF]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 77   Total Tried : 525


The Champion of this Problem (C++) : gs19022 - 0ms / 309byte
My Best Submission (C++) : N/A

[]

Background

이번에 경곽이는 실험실 이사를 위해 포장을 하기로 했다.

경곽이의 실험실에는 N개의 실험도구가 있으며 이들의 무게는 각각 1~4kg으로 모두 정수무게를 가진다.

이번에 포장을 위해서 구입한 상자는 최대 4kg까지의 무게를 견딜 수 있는 상자이다.

실험도구 N개의 무게가 주어질 때, 경곽이는 상자를 최소화 하고자 한다.

만약 실험도구의 무게가 1, 1, 2일 경우 상자 1개에 모두 넣을 수 있다. 따라서 이 경우에는 상자가 1개만 있으면 된다.

경곽이를 도와 최소 상자수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 도구의 수 N이 입력된다.
둘째 줄부터 N개의 무게가 공백으로 구분되어 입력된다. (단, N은 100,000이하의 자연수)

Output

최소 상자의 수를 출력한다.

IO Example

입력1
3
1 1 2

출력1
1

입력2
5
1 2 4 3 3

출력2
4

* 설명 : 입력2의 경우에는 (4), (3, 1), (3), (2)로 포장하면 4개로 포장할 수 있으며, 이보다 더 적은 상자로 포장할 수 있는 방법은 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]