2217: 로프

주어진 로프가 버틸 수 있는 최대 중량으로 들어올릴 수 있는 최대 중량을 구하는 문제이다.

모든 로프를 사용하지 않아도 되며 몇 개의 로프만 골라서 사용해도 된다.

문제에서 각 로프에 걸리는 중량은 모두 w/k 만큼이라고 했기 때문에 선택된 로프가 버틸 수 있는 중량은 이 값보다는 커야한다.
몇 개의 로프를 선택하냐와 어떤 로프를 선택하냐에 따라서 들어올릴 수 있는 최대 중량은 달라진다.

 

 

예를 들어서 로프가 버틸 수 있는 최대 중량으로 10, 3, 6이 주어졌다면

3개를 모두 선택한다면 수식은 w/3이 되고 이 값은 버틸 수 있는 최대 중량의 최소치인 3을 넘길 수는 없기 때문에 들어올릴 수 있는 최대 중량은 3 * 3 = 9가 된다.

하지만 만약 2개를 선택하는데 10, 6만 고른다고 했을 때, 수식은 w/2가 되고 버틸 수 있는 최소 중량이 6이 되기 때문에 들어올릴 수 있는 최대 중량은 2 * 6 = 12가 된다.

 

이 계산식을 정리해보면 주어진 로프가 버틸 수 있는 중량을 오름차순으로 정렬한 후 모두 선택했을 때, 가장 작은 중량을 제외했을 때, 그 다음으로 작은 중량을 제외했을 때 ... 이렇게 차례로 최대 중량을 계산해본 후 가장 많은 중량을 버틸 수 있는 케이스를 정답으로 골라내면 된다.

 

n = int(input())
 
ropes = list()
w_list = list()
for i in range(n):
  get_rope = int(input())
  ropes.append(get_rope)
 
ropes.sort()
k = len(ropes)
for rope in ropes:
  w_list.append(k * rope)
  k -= 1
 
print(max(w_list))