시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB1202522210.945%

문제

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

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

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

입력

입력은 두 줄로 구성된다. 입력 파일의 첫째 줄에는 잘려진 토막들의 총 수 N(1 ≤ N ≤ 100)을 나타낸다. 두 번째 줄에는 작게 잘라진 토막들의 각 길이를 나타내는 정수 N개가 나열된다. 각 토막의 길이를 나타내는 수 사이에는 하나씩의 공백이 있다. 각 토막의 길이는 100보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

9
5 2 1 1 2 5 2 5 1

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIzOTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0IFx1YjljOVx1YjMwMFx1YWUzMCBcdWI5Y2NcdWI0ZTRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJiOVx1YzVmMFx1Yzc3NFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjODE1XHVjMjE4XHVjNzc4IFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWI5YzlcdWIzMDBcdWFlMzBcdWI5N2MgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzQgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHVjNzQ0IFx1YWMwMVx1YWMwMSBcdWM4MTVcdWMyMThcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWMxNlx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDFhMFx1YjljOVx1YzczY1x1Yjg1YyBcdWM1NDRcdWJiMzRcdWI4MDdcdWFjOGNcdWIwOTggXHVjNzk4XHViNzkwXHViMmU0LiBcdWIyZTgsIFx1YzViNFx1YjVhNCBcdWI5YzlcdWIzMDBcdWFlMzBcdWIyOTQgXHVjNzkwXHViOTc0XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWMyYjlcdWM1ZjBcdWM3NzRcdWIyOTQgXHVjNzc0XHViODA3XHVhYzhjIFx1Yzc5OFx1YjgyNFx1YzljNCBcdWQxYTBcdWI5YzlcdWI0ZTRcdWM3NDQgXHViMmU0XHVjMmRjIFx1YmQ5OVx1YzVlY1x1YzExYyBcdWM2ZDBcdWI3OTggXHVjMGMxXHVkMGRjXHVjNzU4IFx1YjljOVx1YjMwMFx1YWUzMFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwIFx1YzZkMFx1Yjc5OCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjM1OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWM3NTggXHVjMjE4XHVjNjQwIFx1YjljOVx1YjMwMFx1YWUzMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNzhhXHVjNWI0XHViYzg0XHViODM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjMmI5XHVjNWYwXHVjNzc0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHViODVjIFx1YmNmNVx1YzZkMFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWM3OThcdWI4MjRcdWM5YzQgXHViYWE4XHViNGUwIFx1ZDFhMFx1YjljOVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWFkNmNcdWMxMzFcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YjljOVx1YjMwMFx1YWUzMCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggJmx0O1x1YWRmOFx1YjliYyZndDtcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIFx1YmNmNFx1YjRlZlx1Yzc3NCBcdWFjMTlcdWM3NDAgXHViOWM5XHViMzAwXHVhZTMwIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVjNzk4XHViNzdjXHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCB7NSwgMiwgMSwgMSwgMiwgNSwgMiwgNSwgMX1cdWM3NzggXHVkMWEwXHViOWM5XHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHViYjM4XHVjODFjXHViMjk0IFx1Yzc3NCBcdWQxYTBcdWI5YzlcdWI0ZTRcdWI4NWNcdWJkODBcdWQxMzAgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWI5YzlcdWIzMDBcdWFlMzAgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCAxMlx1Yzc3OCBcdWFlMzQgXHViOWM5XHViMzAwXHVhZTMwIDJcdWFjMWNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM3M2NcdWIwOTggXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCA2XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwM1wvQklOMDAwMi5qcGdcIiBzdHlsZT1cImhlaWdodDoyMDRweDsgd2lkdGg6MjgxcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI0NTAgXHVjOTA0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5OFx1YjgyNFx1YzljNCBcdWQxYTBcdWI5YzlcdWI0ZTRcdWM3NTggXHVjZDFkIFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAwKVx1Yzc0NCZuYnNwO1x1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkxXHVhYzhjIFx1Yzc5OFx1Yjc3Y1x1YzljNCBcdWQxYTBcdWI5YzlcdWI0ZTRcdWM3NTggXHVhYzAxIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IE5cdWFjMWNcdWFjMDAgXHViMDk4XHVjNWY0XHViNDFjXHViMmU0LiBcdWFjMDEgXHVkMWEwXHViOWM5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4Jm5ic3A7XHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1ZDU1OFx1YjA5OFx1YzUyOVx1Yzc1OCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMWEwXHViOWM5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCZuYnNwOzEwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNmNVx1YWQ2Y1x1YjQxYyBcdWI5YzlcdWIzMDBcdWFlMzBcdWI0ZTRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzOTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdGlja3MiLCJkZXNjcmlwdGlvbiI6IjxwPkdlb3JnZSB0b29rIHN0aWNrcyBvZiB0aGUgc2FtZSBsZW5ndGggYW5kIGN1dCB0aGVtIHJhbmRvbWx5IHVudGlsIGFsbCBwYXJ0cyBiZWNhbWUgYXQgbW9zdCA1MCB1bml0cyBsb25nLiBOb3cgaGUgd2FudHMgdG8gcmV0dXJuIHN0aWNrcyB0byB0aGUgb3JpZ2luYWwgc3RhdGUsIGJ1dCBoZSBmb3Jnb3QgaG93IG1hbnkgc3RpY2tzIGhlIGhhZCBvcmlnaW5hbGx5IGFuZCBob3cgbG9uZyB0aGV5IHdlcmUgb3JpZ2luYWxseS4gUGxlYXNlIGhlbHAgaGltIGFuZCBkZXNpZ24gYSBwcm9ncmFtIHdoaWNoIGNvbXB1dGVzIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBvcmlnaW5hbCBsZW5ndGggb2YgdGhvc2Ugc3RpY2tzLiBBbGwgbGVuZ3RocyBleHByZXNzZWQgaW4gdW5pdHMgYXJlIGludGVnZXJzIGdyZWF0ZXIgdGhhbiB6ZXJvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBzdGlja3MgcGFydHMgYWZ0ZXIgY3V0dGluZy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRoZSBsZW5ndGhzIG9mIHRob3NlIHBhcnRzIHNlcGFyYXRlZCBieSB0aGUgc3BhY2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBmaWxlIGNvbnRhaW5zIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBsZW5ndGggb2Ygb3JpZ2luYWwgc3RpY2tzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

  • 문제의 오타를 찾은 사람: doju
  • 데이터를 추가한 사람: doju