[백준 2217 파이썬] 로프 (실버4, 그리디)

알고리즘 유형 : 그리디
풀이 없이 스스로 풀었나요? : ⭕

---

백준 2217번 로프

솔루션

만약 로프 개수가 5개이고 각 버틸 수 있는 중량이 [10, 19, 20, 21, 40] 이라면

1) 2개의 로프를 사용할 경우

큰 수 2개(21, 40)를 사용하면 버틸 수 있는 최대 중량은 21 * 2 = 42이다.

2) 3개의 로프를 사용할 경우

큰 수 2개(20, 21, 40)를 사용 하면 버틸 수 있는 최대 중량은 20 * 3 = 60이다.

위와 같이 4, 5 일 때에도 적용하면 하나의 식을 찾을 수 있다.

N 개의 로프를 사용하여 버틸 수 있는 최대 중량 = 리스트에서 N 번째로 큰 수 * N

소스 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    ropes = sorted(list(int(input()) for _ in range(n)))
    if n == 1:
        print(ropes[-1])
    else:
        res = 0
        for i in range(2, n + 1):
            tmp = ropes[-i] * i
            if res < tmp:
                res = tmp
        print(res)

---

후기

알고리즘 스터디에서 그리디를 학습 중이라 그리디 관련 문제들을 풀고 있는데
이 문제는 그나마 쉽게 풀 수 있었던 거 같다.