[파이썬] 백준 2217 : 로프

[파이썬] 백준 2217 : 로프

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

2217번: 로프

실버 4

수학, 그리디 알고리즘, 정렬

---

접근 

 

최대 중량이 각각 10, 15인 로프가 들 수 있는 물체의 최대 중량은

10x2 = 20이다.

15가 최대인 밧줄은 15를 들 수 있지만 10이 최대인 밧줄은 10까지 밖에 들 수 없다.

따라서 10 밧줄을 기준으로 생각한다면 10x2 = 20이 들 수 있는 최대 중량이며,

15 밧줄을 기준으로 생각한다면 15 밧줄 하나만 들 때의 15가 최대 중량이 된다.

이중 가장 큰 값은 20이기 때문에 값이 20으로 출력된다.

 

만약 25, 20, 10, 5가 주어진다면 어떻게 할까?

모든 밧줄이 5까지는 버틸 수 있으므로 5x4 = 20이 최대 중량일까?

25가 최대인 밧줄만 사용할 수도 있기 때문에 그렇지 않다.

 

25 밧줄만 사용하면 25를 들 수 있고,

25, 20밧줄을 사용하면 20x2를 들 수 있고,

25, 20, 10밧줄을 사용하면 10x3을 들 수 있고,

25, 20, 10, 5를 모두 사용하면 5x4를 들 수 있다.

 

이 모든 경우들 중 가장 큰 값을 출력하면 답을 구할 수 있다.

 

 

코드 풀이

 

import sys
input = sys.stdin.readline

N = int(input())
lst = [int(input()) for i in range(N)]
lst.sort(reverse=True)
S = [None]*N
for i in range(1, N+1):
    S[i-1] = lst[i-1] * i

print(max(S))

 

그리디 알고리즘을 이용해서 풀기 위해 밧줄의 최대 중량이 큰 순서대로 정렬한다.

 

25 밧줄만 사용하면 25를 들 수 있고,

25, 20밧줄을 사용하면 20x2를 들 수 있고,

25, 20, 10밧줄을 사용하면 10x3을 들 수 있고,

25, 20, 10, 5를 모두 사용하면 5x4를 들 수 있다.

 

따라서 규칙을 정리하면 N번째 밧줄까지 사용했을 때의 최대 무게는 N번째 밧줄의 최대 중량 * N과 같다.

내림차순으로 밧줄을 정렬해두었기 때문에 각각의 밧줄을 하나씩만 사용하는 경우를 굳이 구할 필요가 없다.