boj 2217 : 로프

문제 주소: https://www.acmicpc.net/problem/2217

난이도: silver 4

1.문제설명

• N개의 로프가 있다. 로프마다 들 수 있는 물체의 중량이 다를수 있다.
• 여러개의 로프를 병렬로 연결하면, k개의 로프를 사용해서 중량이 w인 무게를 들어올릴때 로프마다 w/k의 부하가 걸린다.
• 각 로프에 대한 정보가 주어졌을때 로프를 이용해서 들어올릴수 있는 최대중량은?
• 모든 로프를 사용하지 않아도된다.(일부만 사용가능하다)

2.문제해결 아이디어.

• 특정 로프 집합의 들어올릴수 있는 최대중량은 가장 약한 로프에 의해 결정된다.
• 로프 n개가 있다면 이때 최대중량은 가장 약한 로프 * n 이다.

3.문제접근법

• 로프의 정보를 입력받고 오름차순으로 정렬한다.
• 제일 약한 로프에 의해 결정됨으로
  • 로프를 순회하면서 원소 * 로프의 갯수 가 기존의 ans보다 크면 업데이트 시켜준다.
  • n에서 1을 빼서 갯수를 한개 줄여서 다시 해본다.

4.특별히 참고할 사항

• 코드를 치기전에 손으로 써보면 쉽다. 이렇게 말고 minheap으로도 구현할수 있다.

5.코드구현

n = int(input())
ropes = []

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

ans = 0
for rope in ropes:
    if rope*n > ans:
        ans = rope*n
    n -= 1

print(ans)

import heapq
ans = 0
n = int(input())
ropes = []
for i in range(n):
    heapq.heappush(ropes, int(input()))

for i in range(n):
    if ropes[0] * n > ans:
        ans = ropes[0] * n
    heapq.heappop(ropes)
    n -= 1

print(ans)