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

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

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
rope = [int(input()) for _ in range(N)]

rope_descending = list(reversed(sorted(rope)))
result = 0

for i in range(len(rope_descending)):
    result = max(result, rope_descending[i]*(i+1))

print(result)

풀이 요약

1. 로프 한계 중량을 내림차순으로 정렬한다.

2. 첫 번째 단계에서, 1번 로프 대상으로 최대 중량은 1번 로프 한계 중량과 같다.

   두 번째 단계에서, 1~2번 로프 대상으로 최대 중량은, max(1번 로프 한계 중량, 2번 로프 한계 중량 2)이다. 이 때, 로프 한계 중량 15, 10에 대해, 아무리 무거워도 중량을 분산했을 때, 가장 작은 로프인 10 이상으로 분배할 수는 없다. 따라서, 최대 중량은 한계 중량이 가장 작은 로프 로프 개수 이다.

   이런 식으로 마지막 단계까지 진행하면 result에는 모든 로프 대상 최대 중량이 담겨있다.

배운 점, 어려웠던 점

• 그리디 기초