[백준 - Python] 2217. 로프 (그리디)

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

2217번: 로프

 

코드

# 모든 로프를 사용할 필요가 없다

import sys

n = int(sys.stdin.readline())
rope = []
for i in range(n):
    rope.append(int(sys.stdin.readline()))

rope.sort(reverse=True)

mlist = []
while rope:
    rlen = len(rope)
    last = rope.pop()
    mlist.append(last * rlen) # rope[i]*[i+1]

mlist.sort()
print(mlist.pop())

 

여러 개의 로프로 중량을 들면

중량이 로프에 고르게 분산되는데,

각 로프가 감당할 수 있는 무게가 정해져 있음으로

사용할 로프들 중 가장 적은 무게를 들어올리는 로프가 들어올릴 중량에

로프의 개수를 곱해주는 방식으로 최대 하중을 구할 수 있다.

 

문제에서 모든 로프를 사용할 필요는 없고,

임의로 몇 개의 로프를 골라서 사용해도 된다고 명시되어 있다.

 

따라서, 각 로프의 최대 중량을 담고 있는 리스트를 내림차순 정렬해서

감당할 수 있는 최대 하중이 제일 작은 로프부터,

해당 로프를 기준으로 나머지 로프들을 사용했을 시에

나머지 로프들을 활용해 들어 올릴 수 있는 최대 하중을 구한다.

 

그렇게 구한 최대 하중을 최대 하중 리스트에 저장하고

해당 리스트의 최댓값을 구한다.

 

while 문 안의 3줄처럼 코드를 작성해도 되지만,

리스트의 인덱스 값이 사용되는 로프의 개수와 동일하므로

인덱스를 활용하면 len 함수를 사용하지 않을 수 있다. (주석 참고)

 

min, max 함수를 남발하지 말아야 한다.

min, max 함수의 시간 복잡도는 O(N)이다.

sort의 시간 복잡도는 O(NlogN)이다.