양팔저울

면접 대비

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

요약

고정된 규칙으로 저울에 올린 돌들의 최종 차이를 1g부터 100g까지의 추로 맞출 때 필요한 추의 최소 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 시뮬레이션, 그리디
정답자: 아직 제출이 없습니다

문제

$1$ 부터 $n$ 까지 번호가 매겨진 $n$ 개의 자갈이 있다. 다음 절차에 따라 이 자갈들을 양팔저울에 올려놓는다.

$1$ 번 자갈은 왼쪽에, $2$ 번 자갈은 오른쪽에 올려놓는다.
$i = 3, \dots, n$ $i = 3, \dots, n$ 번 자갈마다 차례로 다음 중 하나를 수행한다.
1. 양팔저울이 평형을 이루면, $i$ 번 자갈을 왼쪽에 올려놓는다.
2. 양팔저울이 평형을 이루지 않으면, $i$ 번 자갈을 가벼운 쪽에 올려놓는다.

모든 자갈을 위 규칙에 따라 올려놓은 뒤에도 양팔저울이 평형을 이루지 않을 수 있다. 이 경우 가벼운 쪽에 무게추를 올려 균형을 맞춘다. 무게추는 1g, 2g, 5g, 10g, 20g, 50g, 100g의 7종류가 있으며, 각 종류의 개수에는 제한이 없다.

입력으로 주어진 자갈을 위 규칙에 따라 올렸을 때, 균형을 맞추는 데 추가로 필요한 무게추의 최소 개수를 구하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 자갈 개수를 나타내는 양의 정수 $n$ ( $2 \le n \le 10\,000$ )이 주어진다. 다음 줄에는 $n$ 개의 수가 번호 순서대로 주어지며, 이들은 각 자갈의 무게이다. 자갈의 무게는 각각 1 이상이고, 모든 자갈 무게의 합은 $10\,000\,000$ 이하이다.

출력

출력은 표준출력을 사용한다. 균형을 맞추는 데 추가로 필요한 무게추의 최소 개수를 한 줄에 출력한다.

예제3

예제 1
입력
```
7
3 1 4 1 5 9 2
```
예상 출력
```
2
```
예제 2
입력
```
4
2 4 6 4
```
예상 출력
```
0
```
예제 3
입력
```
5
2 5 3 1 2
```
예상 출력
```
1
```