[백준] 2217 로프 Greedy python 실4

로프가 k개면 각 로프에 w/k만큼 중량이 걸림

 

결국 물건 드는 데 쓰는 로프 중 가장 힘이 약한 로프*k개 만큼만 들 수 있음

 

그래서 로프를 힘 크기 오름차순으로 sort한 후에

 

첫번째 로프(가장 힘이 약한 로프)부터 보면

첫번째 로프*n이 들 수 있는 최대무게

 

두 번째 로프*(n-1)이 최대 무게

세 번째 로프*(n-2)가 최대 무게

 

따라서 i번째에는(i는 0부터 n-1까지)

i번째 힘을 가진 로프*(n-i개)의 값을 구하면 n-i개의 로프를 사용했을 때 들 수 있는 최대 무게를 구할 수 있음

 

결국 이 값들을 다 dp에 저장한 후에

max값을 구하면 됨

 

n = int(input())
arr = [int(input()) for _ in range(n)]

# 로프 k개이면, 각 로프에는 w/k 만큼 중량이 걸림
arr.sort()
ans=[]

for x in arr:
    ans.append(x*n)
    n-=1

print(max(ans))

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