[백준 2217번] 로프

n = int(input())

solution = 0

weight_list = []

for i in range(n):
  weight_list.append(int(input()))

weight_list.sort()
list_len = len(weight_list)

for i in range(list_len):
  temp = (list_len-i)*weight_list[i]
  if temp > solution:
    solution = temp

print(solution)

이번 문제는 로프의 개수를 임의로 정하여 로프가 버틸 수 있는 최대 중량을 구하는 문제이다.

 

이 문제의 핵심은 로프들을 사용하여 각 로프가 w/k 만큼의 중량이 걸리게 된다면, 아무리 평균이 높더라도 결국 (각 로프 중량의 최소 값 * 나머지 로프의 개수) 만큼의 무게밖에 들지 못한다는 것이다. 

 

따라서 먼저 로프가 버틸 수 있는 중량을 오름차순으로 정렬한 뒤, 각 로프의 최소 값과 남은 로프의 개수를 곱하여 가장 최대가 되는 중량을 구하였다.

 

중량이 가장 적은 로프부터 순차적으로 계산한다는 점에서 Greedy 적인 접근이 필요했던 문제였다 :)