[백준/2217/파이썬] 로프

https://www.acmicpc.net/problem/2217

2217번: 로프

Problem

• N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
• 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.]
• 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

조건

• 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

SOL

쉽지않은 문제이다. Greedy를 좀 풀어봐야겠다. 문제를 풀때, insight를 얻어가는 것도 중요하다는걸 또 깨닫게 됩니다.

 

로프가 1개 있다고 해봅시다.  로프가 1개가 있다면, 그 로프가 버틸 수 있는 무게가 최댓값이 될거다. 

이건 문제가 되지않습니다. 왜냐하면 당연한거니까요! 15를 버틸 수 있는 로프가 있다면, 최대 15를 버틸 수 있을겁니다.

 

문제는 로프가 2개가 있을때 부터입니다. 예를들어, 300,100을 버틸 수 있는 로프가 있다고 합시다.

 

최대로 버틸 수 있는 무게를 W라고 생각해봅시다. 그렇다면, 각 로프에 걸리는 부하는 , W/N 입니다. 

(문제의 조건에도 나와있습니다!)

이제, 각 로프에 걸리는 부하 W/N의 최댓값은 어떻게 될까요 ? 

 W/N의 값은 100이 최대일겁니다. 왜냐면, W/N이 100을 넘는 순간, 로프는 끊어질겁니다.

그렇다면, 로프가 2개일 때는, "W"는 200이 될겁니다. 

 

즉, min(rope)* 로프의 갯수가 "W"의 값이 될 수 있는 후보군이고, 이 후보군 들 중, max값이 답이 될겁니다.

 

import sys
input= sys.stdin.readline

N=int(input().rstrip())

nums=[int(input().rstrip()) for _ in range(N)]

nums.sort(reverse=True)
ans=[]
for i in range(1,len(nums)+1):
    ans.append(nums[i-1]*i)

print(max(ans))