동방 특급 열차의 객차
면접 대비시간 제한2초메모리 제한1024 MB
n개 칸의 승객 수가 주어질 때, 한 번의 작업으로 칸 하나를 비우거나 비어 있지 않은 모든 칸에서 승객 한 명씩 내리는 방식으로 전원을 내리는 최소 시간을 구합니다.
문제
기차가 이스탄불에서 런던으로 간다. 기차에는 개의 객차가 있고, 번째 객차에는 명의 승객이 타고 있다. 승객 모두가 종착역인 런던의 빅토리아 역에서 내리려 한다. 객차와 승객이 매우 많아서 하차 계획을 세워야 한다.
단위 시간마다 승무원은 두 가지 중 하나를 할 수 있다. 객차 하나를 통째로 비우거나, 승객이 아직 남아 있는 모든 객차에서 승객을 한 명씩 내리게 한다.
승객은 서두르고 승무원은 당황한 상태다. 기차의 모든 승객을 내리게 하는 데 필요한 최소 시간을 구하라.
입력
첫 번째 줄에 객차의 수 이 주어진다 .
두 번째 줄에는 개의 정수 가 주어진다 . 는 번째 객차의 승객 수이다.
출력
모든 승객을 내리게 하는 데 필요한 최소 시간을 한 줄에 출력한다.