[Greedy/그리디] 백준 2217 로프 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2217번: 로프

 

 

 

2. 문제 풀이

 각 로프가 버틸 수 있는 최대 중량을 구하는 문제입니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 로프가 버틸 수 있는 중량이 W_i인 K개의 로프를 사용했을 때, 각 로프가 버틸 수 있는 최대중량은 W_i * K 입니다.

 따라서 왠만하면 많은 로프를 사용하는 게 좋습니다. 하지만 W_i가 작은 로프가 있으면 다른 로프가 아무리 많은 중량을 버틸 수 있어도, W_i가 작은 로프의 중량으로 최대 중량이 결정됩니다.

 즉, min( W1 * K, W2 *K, ..., Wk *K ) 이기 때문에 W_i가 작은 로프는 제외해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
rope = []
for _ in range(N):
    rope.append(int(input()))

# 내림차순 정렬
rope.sort(reverse=True)

# 그리디 알고리즘
res = 0
for k, w in enumerate(rope, 1):
    res = max(res, w*k)
print(res)

 그리디 알고리즘으로 접근합니다. 최대 중량이 큰 로프부터 사용하며, 사용하는 로프의 개수를 늘려갑니다. 어차피 각 로프가 버틸 수 있는 최대 중량은 '가장 작은 최대 중량을 가진 로프 * k'입니다.

 로프의 개수를 늘려가며, '가장 작은 최대 중량을 가진 로프 * k'의 최댓값을 갱신합니다.