문제
같은 길이의 n개의 밧줄을 이용해서 무거운 물체를 들고자한다.
각 밧줄은 허용가능 무게 t 가 주어져있다. 즉, 밧줄로 t 무게 이하의 물체를 들 때는 별 문제가 없는데, t 무게 보다 무거운 물체를 들게 되면 밧줄은 끊어지게 된다. 하지만 '백지장도 맞들면 낫다'라는 속담이 있듯이 밧줄을 여러 개를 동시에 사용하게 되면 좀 더 무거운 물체를 들 수 있게 된다.
여러 개의 밧줄을 사용하여 하나의 줄도 끊어지지 않고 물체를 들기 위해선 다음과 같은 조건을 만족해야한다.
- 물체의 무게를 w, 사용하는 밧줄의 개수를 k 라고 하자.
- 사용하고자 하는 밧줄을 각각 1, 2, ... , k 번 밧줄이라고 하자.
- 그리고 i 번 밧줄의 허용 가능 무게 t 를 t_i 라고 하자.
- 모든 밧줄이 w / k <= t_i 를 만족할 경우 해당 물체를 들 수 있다.
예를 들어 1, 10, 15의 허용 무게를 가지는 밧줄이 주어졌을 경우에 10, 15를 사용하게 되면 무게가 20인 물체를 들 수 있게 된다.
여러 개의 밧줄의 허용무게가 입력되었을 때, 이 밧줄들을 조합하여 가장 많이 들어 올릴 수 있는 물체의 최대 무게를 출력하는 프로그램을 작성하라.
입력
첫 번째 줄에는 밧줄의 개수 N (1 <= N <= 1,000)이 주어진다.
그 다음 줄에는 N개의 밧줄의 허용무게가 주어지는데 이는 1 이상 10,000 이하의 정수로 들어온다.
출력
입력된 밧줄들의 조합을 통해 들어 올릴 수 있는 가장 무거운 물체의 무게를 출력한다. 무게는 반드시 정수로 출력되어야 한다.
예제
3
10 1 15
20
로그인해야 코드를 작성할 수 있어요.