소는 왜 길을 건너갔을까? 3 timer 2s memory 512MB

이웃 농장의 소가 길을 건너오는 것에 화가 난 존은 농장 둘레에 매우 큰 울타리를 지었다. 이 일로 주변 소들은 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문에 화가 났다.

이웃 농장의 소들은 이제 존의 농장에 방문하기 위해서 문을 통과해야 하는데, 문을 통과 하려면 존의 검문을 받아야 한다. 여러 마리의 소가 한 번에 들어가려고 하면 병목 현상이 일어나 줄이 길어진다.

어느 날 N마리의 소가 존의 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다양하다. 존의 몸은 하나기에 두 소가 동시에 검문을 받을 수는 없다.

예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있고, 8초에 도착한 소가 1초 동안 검문을 받는다면 두 소가 모두 농장에 입장하기 위해 총 13초가 소모된다.

모든 소가 농장에 입장하려면 몇 초가 걸리는 지 계산해보자.