[백준] 로프 - Python

Juppi·2022년 5월 24일
0

문제 설명

주어진 로프들을 연결했을 때 하중이 고르게 분산된다.
k개의 로프가 있고, 하중에 w라고 할때, k개의 로프를 모두 연결하면 w/k 의 하중이 각 로프게 고르게 걸린다.
입력으로 각 로프가 버틸 수 있는 최대하중이 주어질 때, 로프들을 사용하여 버틸 수 있는 전체 하중의 최댓값을 구하는 문제이다. 이 때, 로프는 다 사용하지 않아도 된다 !

접근 방법

k개의 로프가 존재할때 각 로프의 최대 하중을 kik_i 라고 하고, i는 사용한 로프의 갯수라고 하자.
로프를 하나씩 추가하면서 버틸 수 있는 하중의 최댓값을 갱신해 나가며 풀면되는 것이다.

[35, 7, 20, 15] 라는 4개의 로프가 주어졌을때, 리스트의 요소를 하나씩 추가하면서 최대값을 갱신해보자. 반복문에 들어가기전, 최대한 많이 버틸 수 있는 로프들로만 이루어진 로프가 당연히 좋으므로, 내림차순 정렬을 하고 들어가자 !

  • i=0 일때, 로프는 35만 존재한다. 이때 버틸 수 있는 최대 무게는 35이다 (35 * 1, max=35)
  • i=1 일때, 로프는 35, 20이 존재한다. 이때 버틸 수 있는 최대 무게는 존재하는 로프중 최솟값을 가지고 계산해야한다. (20 * 2, max=40)
  • i=2 일때, 로프는 35, 20, 15 이 존재한다. 이때 버틸 수 있는 최대 무게는 45이다. (15 3, max = 45)
    -i=3 일때, 로프는 35, 20, 15, 7이 존재한다. 이때 버틸 수 있는 최대 무게는 28이다. (7
    4, max = 45)

내림차 순으로 정렬 후, 세 개까지의 로프를 사용했을 때의 하중이 최대하중인 것을 알 수 있다 !

코드

num = int(input())

ropes = list()
for i in range(num):
  ropes.append(int(input()))
ropes.sort(reverse=True)

max = 0
for i in range(len(ropes)):
  if max < (i+1)*ropes[i]:
    max = (i+1)*ropes[i]

print(max)

문제 링크

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

profile
잠자면서 돈버는 그날까지

0개의 댓글