BOJ 2217 로프

문제

접근 방법

들어올릴 수 있는 물체의 최대 무게는 사용하는 로프들 중 하나의 로프로 들 수 있는 중량의 최솟값 * 로프의 개수, 또는 각자가 들 수 있는 중량을 계산해서 구할 수 있다.

각자가 들 수 있는 중량을 포함하는 이유는 분산을 한다고 꼭 더 큰 무게를 들 수 있는 것이 아니기 때문이다. 예를 들어 두 로프가 각각 1과 10만큼 들 수 있다면 분산을 한다면 들 수 있는 총 무게는 2이지만, 각자가 들 수 있는 무게의 최댓값은 10이다.

정리하자면, 계속해서 로프가 감당할 수 있는 무게의 최솟값과 그 값보다 큰 로프들의 개수의 곱을 구하는 문제이므로 그리디 알고리즘이라고 볼 수 있다.

정답 코드

import sys
input = sys.stdin.readline

"""
들어올릴 수 있는 물체의 최대 무게는 사용하는 로프가 들 수 있는 중량의 최솟값 * 로프의 개수, 또는 각자가 들 수 있는 중량을 계산해서 구할 수 있다.

로프가 들 수 있는 중량들을 오름차순으로 정렬

앞에서부터 iterate하면서 ropes[i]*(n-i)으로 계산

"""

n = int(input())

ropes = []

results = []
max_ans = 0

for _ in range(n):
  rope = int(input())
  ropes.append(rope)
  max_ans = max(max_ans, rope)

ropes.sort()

for i in range(n):
  max_ans =  max(max_ans, ropes[i]*(n-i))

print(max_ans)