Informatica Online Judge

  같은 길이 막대 만들기 (Large) [0344 / 0158]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 120   Total Tried : 245


The Champion of this Problem (C++) : gs18119 - ms / 676byte
My Best Submission (C++) : N/A

[]

Background

승연이는 길이가 정수인 동일한 막대기를 여러 개 가지고 있는데, 이 막대기들을 각각 정수의 길이를 갖는 여러 개의 토막으로 아무렇게나 잘랐다. 단, 어떤 막대기는 자르지 않을 수도 있다. 승연이는 이렇게 잘려진 토막들을 다시 붙여서 원래 상태의 막대기로 만들려고 하는데 원래 자기가 가지고 있던 막대기의 수와 막대기의 길이를 잊어버렸다. 그래서 승연이는 길이가 모두 같은 가장 짧은 막대기들로 복원하기로 하였다.
문제는 잘려진 모든 토막으로부터 구성될 수 있는 같은 길이의 막대기 중에서 가장 짧은 길이를 계산하는 프로그램을 작성하는 것이다.
아래 <그림>의 예에서 보듯이 같은 막대기 몇 개를 잘라서 길이가 {5,2,1,1,2,5,2,5,1}인 토막으로 만들었다. 문제는 이 토막들로부터 구할 수 있는 같은 길이의 막대기 중에서 가장 짧은 것을 구하는 것이다. 아래 그림의 예에서 길이가 12인 긴 막대기 2개를 만들 수도 있으나 가장 짧은 동일한 막대기들의 길이는 6이 된다.

Input

첫 번째 줄에 막대의 갯수 n이 입력된다. (n은 50이하의 자연수)
두 번째 줄에 n개의 막대들의 길이가 공백으로 구분되어 입력된다. (단, 각 막대의 길이는 500 이하의 자연수.)

Output

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

IO Example

입력
9
5 2 1 1 2 5 2 5 1

출력
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]