뮤탈리스크

면접 대비

시간 제한2초메모리 제한512 MB

요약

SCV가 최대 3마리일 때, 서로 다른 SCV에 9, 3, 1의 피해를 주는 공격을 최소 몇 번 해야 모두 파괴할 수 있는지 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

수빈이는 강호와 스타크래프트를 하고 있다. 수빈이에게는 뮤탈리스크 한 마리가 남았고, 강호에게는 SCV $N$ 대가 남았다. SCV는 뮤탈리스크를 공격하지 못하므로 승패는 이미 갈렸다. 남은 문제는 SCV를 모두 파괴하는 데 공격을 몇 번 해야 하는지다.

뮤탈리스크는 한 번 공격할 때 서로 다른 SCV를 최대 세 대까지 공격할 수 있다.

첫 번째로 공격받는 SCV는 체력 9를 잃는다.
두 번째로 공격받는 SCV는 체력 3을 잃는다.
세 번째로 공격받는 SCV는 체력 1을 잃는다.

한 번의 공격에서 같은 SCV를 두 번 이상 공격할 수는 없다. SCV의 체력이 0 이하가 되면 그 즉시 파괴된다.

남은 SCV의 체력이 주어질 때, 모든 SCV를 파괴하는 데 필요한 공격 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 SCV의 수 $N$ ( $1 \le N \le 3$ )이 주어진다. 둘째 줄에 SCV $N$ 대의 체력이 공백으로 구분되어 주어진다. 체력은 60 이하의 자연수다.

출력

모든 SCV를 파괴하는 데 필요한 공격 횟수의 최솟값을 첫째 줄에 출력한다.

힌트

체력이 12, 10, 4인 SCV 세 대를 생각해 보자. 1번, 3번, 2번 순서로 공격하면 남은 체력은 $(12-9, 10-1, 4-3) = (3, 9, 1)$ 이 된다. 이어서 2번, 1번, 3번 순서로 공격하면 $(3-3, 9-9, 1-1) = (0, 0, 0)$ 이 되어 두 번의 공격으로 끝난다.

예제5

예제 1
입력
```
3
12 10 4
```
예상 출력
```
2
```
예제 2
입력
```
3
54 18 6
```
예상 출력
```
6
```
예제 3
입력
```
1
60
```
예상 출력
```
7
```
예제 4
입력
```
3
1 1 1
```
예상 출력
```
1
```
예제 5
입력
```
2
60 40
```
예상 출력
```
9
```