시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB91241625242.353%

문제

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

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

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

입력

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

출력

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

예제 입력 1

2
3 3

예제 출력 1

1

예제 입력 2

3
1 1 1

예제 출력 2

1

예제 입력 3

5
4 3 5 7 9

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjI3ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWM3NzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWFkZjhcdWM3NTggXHViMmU0XHViNzdkXHViYzI5XHVjNWQwXHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjY2I0XHVjNzc4XHVjNzQ0IFx1Y2MzZVx1YzU1OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2NiNFx1Yzc3OFx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YWNlMFx1YjlhY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhY2UwXHViOWFjXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFjZTBcdWI5YWNcdWI5N2MgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjZTBcdWI5YWNcdWIyOTQgXHVjNWY0XHVhY2UwIFx1YjJlYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMsIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NThcdWFjNzBcdWIwOTggXHViNDUwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWM1ZWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWUzNCBcdWNjYjRcdWM3NzhcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YzgwMVx1Yzc0MCBcdWFjZTBcdWI5YWNcdWI5N2MgXHVjNWY0XHVhY2UwIFx1YjJlYlx1YzU0NFx1YzExYywgXHViYWE4XHViNGUwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhZTM0IFx1Y2NiNFx1Yzc3OFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1Y2NiNFx1Yzc3OFx1Yzc3NCBcdWFjZTBcdWI5YWMgXHVkNTU4XHViMDk4XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzVmNFx1YzViNFx1YzExYyBcdWIwOThcdWJhMzhcdWM5YzAgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAgXHViMmViXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNzUzYjhmOS05YjViLTQ2NDQtOWNmOS1hMDA3NzE1MzBkZTZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE1MnB4OyBoZWlnaHQ6IDEzMXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWNjYjRcdWM3NzhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWUzNCBcdWNjYjRcdWM3NzhcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWJiMzZcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWM1ZjRcdWFjZTAgXHViMmViXHVjNTQ0XHVjNTdjXHVkNTYwIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWFjZTBcdWI5YWMgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YzU0NFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NiNFx1Yzc3OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTiAoMiAmbGU7IE4gJmxlOyA1MDAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2NiNFx1Yzc3OFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBMPHN1Yj5pPFwvc3ViPigxICZsZTsgTDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhY2UwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMQU5DSSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGZvdW5kIE4gY2hhaW5zIGluIGhpcyBhdHRpYy4gRWFjaCBjaGFpbiBjb25zaXN0cyBvZiBzb21lIG51bWJlciBvZiBsaW5rcywgd2hlcmUgZWFjaCBsaW5rIGhhcyBhdCBtb3N0IHR3byBhZGphY2VudCBsaW5rcy4gRWFjaCBsaW5rIGNhbiBiZSBvcGVuZWQgb3IgY2xvc2VkLCBzbyBpdCBpcyBwb3NzaWJsZSB0byBzZXBhcmF0ZSBjaGFpbnMgb3IgY29ubmVjdCB0aGVtIGludG8gYSBsb25nZXIgY2hhaW4uIE1pcmtvIHdvdWxkIGxpa2UgdG8gY29ubmVjdCBhbGwgY2hhaW5zIGludG8gb25lIGh1Z2UgY2hhaW4sIHdoaWxlIG9wZW5pbmcgYW5kIGNsb3NpbmcgYXMgZmV3IGxpbmtzIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgTWlya28gaGFzIG9ubHkgdGhyZWUgY2hhaW5zLCBlYWNoIGNvbnNpc3Rpbmcgb2Ygb25seSBvbmUgbGluaywgaGUgY2FuIG9wZW4gb25lIG9mIHRoZW0sIHVzZSBpdCB0byBjb25uZWN0IHRoZSByZW1haW5pbmcgdHdvIGFuZCBjbG9zZSBpdDo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNzUzYjhmOS05YjViLTQ2NDQtOWNmOS1hMDA3NzE1MzBkZTZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE1MnB4OyBoZWlnaHQ6IDEzMXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbnVtYmVyIG9mIGNoYWlucyBhbmQgdGhlIGxlbmd0aCBvZiBlYWNoIGNoYWluLCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBsaW5rcyB0aGF0IE1pcmtvIGhhcyB0byBvcGVuIGFuZCBjbG9zZSBpbiBvcmRlciB0byBiaW5kIHRoZW0gYWxsIGluIGRhcmtuZXNzIG9uZSBsb25nIGNoYWluLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyA1MDAgMDAwKSwgdGhlIG51bWJlciBvZiBjaGFpbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIHBvc2l0aXZlIGludGVnZXJzIEw8c3ViPmk8XC9zdWI+ICgxICZsZTsgTDxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDApLCB0aGUgbGVuZ3RocyBvZiBpbmRpdmlkdWFsIGNoYWluczxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gbnVtYmVyIG9mIGxpbmtzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogTWlya28gY2FuIG9wZW4gdGhlIGxhc3QgbGluayBvZiB0aGUgZmlyc3QgY2hhaW4sIGNvbm5lY3QgaXQgd2l0aCB0aGUgZmlyc3QgbGluayBvZiB0aGUgc2Vjb25kIGNoYWluIGFuZCBjbG9zZSBpdC48XC9wPlxyXG5cclxuPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgdGhpcmQgZXhhbXBsZTogSGVyZSBpdCBpcyBiZXN0IHRvIGNvbXBsZXRlbHkgdGFrZSBhcGFydCB0aGUgY2hhaW4gb2YgbGVuZ3RoIDMsIHVzaW5nIGl0cyB0aHJlZSBsaW5rcyB0byBjb25uZWN0IHRoZSByZW1haW5pbmcgY2hhaW5zLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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