시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 218 15 9 12.857%

문제

승연이는 길이가 정수인 동일한 막대기를 여러 개 가지고 있는데, 이 막대기들을 각각 정수의 길이를 갖는 여러 개의 토막으로 아무렇게나 잘랐다. 단, 어떤 막대기는 자르지 않을 수도 있다. 승연이는 이렇게 잘려진 토막들을 다시 붙여서 원래 상태의 막대기로 만들려고 하는데 원래 자기가 가지고 있던 막대기의 수와 막대기의 길이를 잊어버렸다. 그래서 승연이는 길이가 모두 같은 가장 짧은 막대기들로 복원하기로 하였다.

문제는 잘려진 모든 토막으로부터 구성될 수 있는 같은 길이의 막대기 중에서 가장 짧은 길이를 계산하는 프로그램을 작성하는 것이다.

아래 <그림>의 예에서 보듯이 같은 막대기 몇 개를 잘라서 길이가 {5,2,1,1,2,5,2,5,1}인 토막으로 만들었다. 문제는 이 토막들로부터 구할 수 있는 같은 길이의 막대기 중에서 가장 짧은 것을 구하는 것이다. 아래 그림의 예에서 길이가 12인 긴 막대기 2개를 만들 수도 있으나 가장 짧은 동일한 막대기들의 길이는 6이 된다.

입력

입력은 두 줄로 구성된다. 입력 파일의 첫째 줄에는 잘려진 토막들의 총 수를 나타낸다. 두 번째 줄에는 작게 잘라진 토막들의 각 길이를 나타내는 정수가 나열된다. 각 토막의 길이를 나타내는 숫자 사이에는 하나씩의 공백이 있다. 각 토막의 길이 i 은 2≤i≤50 인 정수이다.

출력

첫째 줄에 복구된 막대기들의 길이를 나타내는 정수를 출력한다.

예제 입력 1

9
5 2 1 1 2 5 2 5 1

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIzOTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0IFx1YjljOVx1YjMwMFx1YWUzMCBcdWI5Y2NcdWI0ZTRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJiOVx1YzVmMFx1Yzc3NFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjODE1XHVjMjE4XHVjNzc4IFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWI5YzlcdWIzMDBcdWFlMzBcdWI5N2MgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzQgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHVjNzQ0IFx1YWMwMVx1YWMwMSBcdWM4MTVcdWMyMThcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWMxNlx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDFhMFx1YjljOVx1YzczY1x1Yjg1YyBcdWM1NDRcdWJiMzRcdWI4MDdcdWFjOGNcdWIwOTggXHVjNzk4XHViNzkwXHViMmU0LiBcdWIyZTgsIFx1YzViNFx1YjVhNCBcdWI5YzlcdWIzMDBcdWFlMzBcdWIyOTQgXHVjNzkwXHViOTc0XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWMyYjlcdWM1ZjBcdWM3NzRcdWIyOTQgXHVjNzc0XHViODA3XHVhYzhjIFx1Yzc5OFx1YjgyNFx1YzljNCBcdWQxYTBcdWI5YzlcdWI0ZTRcdWM3NDQgXHViMmU0XHVjMmRjIFx1YmQ5OVx1YzVlY1x1YzExYyBcdWM2ZDBcdWI3OTggXHVjMGMxXHVkMGRjXHVjNzU4IFx1YjljOVx1YjMwMFx1YWUzMFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwIFx1YzZkMFx1Yjc5OCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjM1OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWM3NTggXHVjMjE4XHVjNjQwIFx1YjljOVx1YjMwMFx1YWUzMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNzhhXHVjNWI0XHViYzg0XHViODM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjMmI5XHVjNWYwXHVjNzc0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHViODVjIFx1YmNmNVx1YzZkMFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWM3OThcdWI4MjRcdWM5YzQgXHViYWE4XHViNGUwIFx1ZDFhMFx1YjljOVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWFkNmNcdWMxMzFcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YjljOVx1YjMwMFx1YWUzMCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggJmx0O1x1YWRmOFx1YjliYyZndDtcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIFx1YmNmNFx1YjRlZlx1Yzc3NCBcdWFjMTlcdWM3NDAgXHViOWM5XHViMzAwXHVhZTMwIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVjNzk4XHViNzdjXHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCB7NSwyLDEsMSwyLDUsMiw1LDF9XHVjNzc4IFx1ZDFhMFx1YjljOVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWM3NzQgXHVkMWEwXHViOWM5XHViNGU0XHViODVjXHViZDgwXHVkMTMwIFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWFlMzhcdWM3NzRcdWM3NTggXHViOWM5XHViMzAwXHVhZTMwIFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyBcdWFlMzhcdWM3NzRcdWFjMDAgMTJcdWM3NzggXHVhZTM0IFx1YjljOVx1YjMwMFx1YWUzMCAyXHVhYzFjXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjNzNjXHViMDk4IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YjljOVx1YjMwMFx1YWUzMFx1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgNlx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDNcL0JJTjAwMDIuanBnXCIgc3R5bGU9XCJoZWlnaHQ6MjA0cHg7IHdpZHRoOjI4MXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3OThcdWI4MjRcdWM5YzQgXHVkMWEwXHViOWM5XHViNGU0XHVjNzU4IFx1Y2QxZCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3OTFcdWFjOGMgXHVjNzk4XHViNzdjXHVjOWM0IFx1ZDFhMFx1YjljOVx1YjRlNFx1Yzc1OCBcdWFjMDEgXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHViMDk4XHVjNWY0XHViNDFjXHViMmU0LiBcdWFjMDEgXHVkMWEwXHViOWM5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjJiXHVjNzkwIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM1MjlcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDFhMFx1YjljOVx1Yzc1OCBcdWFlMzhcdWM3NzQgaSBcdWM3NDAgMiZsZTtpJmxlOzUwIFx1Yzc3OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjZjVcdWFkNmNcdWI0MWMgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RpY2tzIiwiZGVzY3JpcHRpb24iOiI8cD5HZW9yZ2UgdG9vayBzdGlja3Mgb2YgdGhlIHNhbWUgbGVuZ3RoIGFuZCBjdXQgdGhlbSByYW5kb21seSB1bnRpbCBhbGwgcGFydHMgYmVjYW1lIGF0IG1vc3QgNTAgdW5pdHMgbG9uZy4gTm93IGhlIHdhbnRzIHRvIHJldHVybiBzdGlja3MgdG8gdGhlIG9yaWdpbmFsIHN0YXRlLCBidXQgaGUgZm9yZ290IGhvdyBtYW55IHN0aWNrcyBoZSBoYWQgb3JpZ2luYWxseSBhbmQgaG93IGxvbmcgdGhleSB3ZXJlIG9yaWdpbmFsbHkuIFBsZWFzZSBoZWxwIGhpbSBhbmQgZGVzaWduIGEgcHJvZ3JhbSB3aGljaCBjb21wdXRlcyB0aGUgc21hbGxlc3QgcG9zc2libGUgb3JpZ2luYWwgbGVuZ3RoIG9mIHRob3NlIHN0aWNrcy4gQWxsIGxlbmd0aHMgZXhwcmVzc2VkIGluIHVuaXRzIGFyZSBpbnRlZ2VycyBncmVhdGVyIHRoYW4gemVyby48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2Ygc3RpY2tzIHBhcnRzIGFmdGVyIGN1dHRpbmcuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgbGVuZ3RocyBvZiB0aG9zZSBwYXJ0cyBzZXBhcmF0ZWQgYnkgdGhlIHNwYWNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZmlsZSBjb250YWlucyB0aGUgc21hbGxlc3QgcG9zc2libGUgbGVuZ3RoIG9mIG9yaWdpbmFsIHN0aWNrcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 1995 H번

  • 문제의 오타를 찾은 사람: doju