COCI 2012/2013 Contest 2 LANCI- 체인 > 문제은행 : 정보올림피아드&알고리즘




1944 : 체인

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
19 회   
시도횟수
65 회   

문제

찬식이는 로봇 제작 키트를 이용해서 로봇을 만들다가 

체인이 필요해서 키트를 뒤졌더니 체인이 붙은 채로 N조각이 발견되었다. 

각 체인은 Li개의 고리가 일렬로 연결된 채로 발견되었다.


찬식이는 N조각의 체인들을 아래와 같은 방법으로 연결해서 하나의 '일렬로 연결된' 체인을 만들 것이다.


 


 


 


 


1. 고리 하나를 연다.

2. 그 고리를 다른 고리에 끼운다.

3. 고리를 다시 닫는다.


찬식이가 최소 몇 개의 고리를 열어야 N개의 체인을 모두 연결시킬 수 있을지 구하는 프로그램을 작성하여라.

 


입력형식

첫 번째 줄에는 체인의 수 N이 주어진다. (2 ≤ N ≤ 500,000)
두 번째 줄에는 각 체인을 이루고 있는 고리의 수 Li가 주어진다. (1 ≤ Li ≤ 1,000,000)


출력형식

찬식이가 N개의 체인을 모두 연결시키기 위해서 열어야 하는 고리의 수의 최솟값을 출력한다.


입력 예

2
3 3

출력 예

1

입력 예

3
1 1 1

출력 예

1

입력 예

5
4 3 5 7 9

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP