[BOJ-2217] 로프 (Python)

🤒 문제

BOJ-2217 로프

💊 풀이

1. 예를들어, 로프가 버틸 수 있는 최대 중량이 10, 15, 20, 35, 30 가 있다고 해보자.

2. 이 리스트를 내림차순으로 정렬한다.
   35, 30, 20, 15, 10

3. 만약 로프를 1개쓴다면, 최대중량은 35다.

4. 만약 로프를 2개쓰고, 최대중량을 W 라고 하자.
   그럼 한 로프가 들 수 있는 최대중량은 (W / 로프갯수), 즉 W/2 일 것이다.
   내림차순으로 로프 두개면 35, 30 이고, 그렇게 되면 W/2 <= 30 가 될것이다. 왜냐면, 로프 두개를 써야하는데 W/2가 30보다 크게되면 로프를 하나밖에 못 쓰기 때문이다.

그리고 나서 천천히 생각해 보면, 답은

각 로프가 버틸 수 있는 최대 중량 리스트를 내림차순 으로 정렬하고 로프를 i+1 개 썼을 때의 최대중량 W는,
W = 정렬된 리스트의 i번째 원소 * (i + 1)

라는 것을 알 수 있다.

다 풀고나서 인터넷에 다른 분들의 풀이를 많이 찾아봤는데, 저 W를 구하는 식을 for문을 통해 돌리는 풀이가 많았다. 근데 그렇게 되면 시간복잡도가 $O(N^{2})$ 이 되기 때문에 비추이다.

heapq를 사용하면 heappush() 는 시간복잡도가 $O(logN)$ 으로, 이것을 N번 반복하므로 $O(NlogN)$ 의 시간 복잡도를 얻을 수 있다. 더 좋은 자료구조가 생각난다면 좋겠지만 지금 내가 생각나는것 중에선 힙이 최선이다😉 파이썬의 heapq 모듈은 따로

• heapq 모듈에 대해 정리한 글

에 정리해 놓았다.

✨ 소스코드

import sys
import heapq

N = int(input())
weight = [int(sys.stdin.readline()) for _ in range(N)]
weight.sort(reverse = True) # 내림차순으로 정렬

result = []

for i in range(N):
    heapq.heappush(result, -weight[i] * (i + 1))

print(-heapq.heappop(result))

heappop() 는 $O(logN)$ 의 시간 복잡도를 가지기 때문에, 마지막 프린트문을

print(-result[0]) # 최대힙의 루트값

으로 바꾸면,
가 된다.