[백준] 2217 파이썬(python) : 로프 - (★)

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

2217번: 로프

 

 

import sys
n = int(sys.stdin.readline())
lope = []
for _ in range(n):
    lope.append(int(sys.stdin.readline())) #1
lope.sort(reverse=True) #2
for i in range(n):
    lope[i] = lope[i]*(i+1) #3
print(max(lope)) #4

 

모든 로프를 사용할 필요는 없고 사용한 로프들을 이용하여 들어올릴 수 있는 로프의 최댓값을 구하는 문제다.

'가장 작은 무게를 버틸 수 있는 로프 * 병렬로 연결된 로프의 개수'가 정답이된다.

병렬로 로프가 연결되었을때 중량은 모두 고르게 w/k만큼이라고 했으므로 최솟값이 기준이 된다.

[10, 15]인 예제에서 가장 작은 하중을 견딜 수 있는 로프는 10이고 로프의 수는 2이므로 10*2= 20이 정답이 된다.

하지만 이건 모든 로프를 사용했을 경우이고 문제에선 로프를 전부 사용하지 않아도 된다고 했다. w/k들의 합이 최댓값일대의 값을 출력해야 하므로 만일 입력이 [4, 20]라면 모두 사용할때 가장 작은 하중은 4이고 로프의 개수는 2 이므로 4*2 = 8이 되는데 20로프 한개만을 사용했을때는 20*1 = 20으로 최댓값이 된다.

 

그래서 모든 로프를 사용하지 않아도 최댓값이 나오는 경우가 있다면 그 때를 출력해줘야 한다.

그러기 위해 내림차순으로 정렬을 한다. 정렬 후 각 값에 인덱스의+1한 값을 곱해준다면 그 위치에서의 최소하중*사용된 루프의 개수가 된다. 그리고 리스트 중 가장 큰값을 출력하면 원하는 정답이 된다.

 

#1 : n의 개수만큼 입력받음

#2 : 내림차순 정렬

#3 : 각 인덱스에서의 '최소하중*사용된 루프의 개수'로 리스트를 재구성

#4 : 리스트 중 최댓값을 출력하면 하중의 최댓값이 된다.