시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 151 62 57 46.341%

문제

희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그래서, 체인을 분리하거나 두 체인을 연결하여 하나의 긴 체인으로 만들 수 있다. 희원이는 가능한 한 적은 고리를 열고 닫아서, 모든 체인을 하나의 긴 체인으로 연결하려고 한다.

예를 들어, 희원이가 세 개의 체인을 가지고 있고, 각 체인이 고리 하나로만 이루어져 있다면, 그 중 하나를 열어서 나머지 두 개를 연결하고 닫으면 된다.

체인의 개수와 각각의 체인의 길이가 주어지면, 하나의 긴 체인으로 모든 체인을 묶기 위해 희원이가 열고 닫아야할 최소한의 고리 수를 찾아라.

입력

첫 번째 줄에는 체인의 개수를 나타내는 양의 정수 N (2 ≤ N ≤ 500000)이 주어진다. 두 번째 줄에는 각각의 체인의 길이를 나타내는 N개의 양의 정수 Li(1 ≤ Li ≤ 1000000)가 주어진다.

출력

첫째 줄에 필요한 고리의 최소 개수를 출력한다.

예제 입력 1

5
4 3 5 7 9

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjI3ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWM3NzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWFkZjhcdWM3NTggXHViMmU0XHViNzdkXHViYzI5XHVjNWQwXHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjY2I0XHVjNzc4XHVjNzQ0IFx1Y2MzZVx1YzU1OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2NiNFx1Yzc3OFx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YWNlMFx1YjlhY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhY2UwXHViOWFjXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFjZTBcdWI5YWNcdWI5N2MgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjZTBcdWI5YWNcdWIyOTQgXHVjNWY0XHVhY2UwIFx1YjJlYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMsIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NThcdWFjNzBcdWIwOTggXHViNDUwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWM1ZWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWUzNCBcdWNjYjRcdWM3NzhcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YzgwMVx1Yzc0MCBcdWFjZTBcdWI5YWNcdWI5N2MgXHVjNWY0XHVhY2UwIFx1YjJlYlx1YzU0NFx1YzExYywgXHViYWE4XHViNGUwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhZTM0IFx1Y2NiNFx1Yzc3OFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1Y2NiNFx1Yzc3OFx1Yzc3NCBcdWFjZTBcdWI5YWMgXHVkNTU4XHViMDk4XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzVmNFx1YzViNFx1YzExYyBcdWIwOThcdWJhMzhcdWM5YzAgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAgXHViMmViXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGFpbi5wbmdcIiBzdHlsZT1cIndpZHRoOiAxODZweDsgaGVpZ2h0OiAxMzdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjY2I0XHVjNzc4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjY2I0XHVjNzc4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFlMzQgXHVjY2I0XHVjNzc4XHVjNzNjXHViODVjIFx1YmFhOFx1YjRlMCBcdWNjYjRcdWM3NzhcdWM3NDQgXHViYjM2XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjNWY0XHVhY2UwIFx1YjJlYlx1YzU0NFx1YzU3Y1x1ZDU2MCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVhY2UwXHViOWFjIFx1YzIxOFx1Yjk3YyBcdWNjM2VcdWM1NDRcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYjRcdWM3NzhcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgNTAwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTDxzdWI+aTxcL3N1Yj4oMSAmbGU7IEw8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWNlMFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTEFOQ0kiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBmb3VuZCBOIGNoYWlucyBpbiBoaXMgYXR0aWMuIEVhY2ggY2hhaW4gY29uc2lzdHMgb2Ygc29tZSBudW1iZXIgb2YgbGlua3MsIHdoZXJlIGVhY2ggbGluayBoYXMgYXQgbW9zdCB0d28gYWRqYWNlbnQgbGlua3MuIEVhY2ggbGluayBjYW4gYmUgb3BlbmVkIG9yIGNsb3NlZCwgc28gaXQgaXMgcG9zc2libGUgdG8gc2VwYXJhdGUgY2hhaW5zIG9yIGNvbm5lY3QgdGhlbSBpbnRvIGEgbG9uZ2VyIGNoYWluLiBNaXJrbyB3b3VsZCBsaWtlIHRvIGNvbm5lY3QgYWxsIGNoYWlucyBpbnRvIG9uZSBodWdlIGNoYWluLCB3aGlsZSBvcGVuaW5nIGFuZCBjbG9zaW5nIGFzIGZldyBsaW5rcyBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIE1pcmtvIGhhcyBvbmx5IHRocmVlIGNoYWlucywgZWFjaCBjb25zaXN0aW5nIG9mIG9ubHkgb25lIGxpbmssIGhlIGNhbiBvcGVuIG9uZSBvZiB0aGVtLCB1c2UgaXQgdG8gY29ubmVjdCB0aGUgcmVtYWluaW5nIHR3byBhbmQgY2xvc2UgaXQ6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hhaW4ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM3cHg7IG9wYWNpdHk6MC45OyB3aWR0aDoxODZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbnVtYmVyIG9mIGNoYWlucyBhbmQgdGhlIGxlbmd0aCBvZiBlYWNoIGNoYWluLCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBsaW5rcyB0aGF0IE1pcmtvIGhhcyB0byBvcGVuIGFuZCBjbG9zZSBpbiBvcmRlciB0byBiaW5kIHRoZW0gYWxsIGluIGRhcmtuZXNzIG9uZSBsb25nIGNoYWluLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyA1MDAgMDAwKSwgdGhlIG51bWJlciBvZiBjaGFpbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIHBvc2l0aXZlIGludGVnZXJzIEw8c3ViPmk8XC9zdWI+ICgxICZsZTsgTDxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDApLCB0aGUgbGVuZ3RocyBvZiBpbmRpdmlkdWFsIGNoYWluczxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gbnVtYmVyIG9mIGxpbmtzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 3번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: jh05013