[Beakjoon] 2217 : 로프 - python

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

 

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

 

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

▶️ 입력 조건 

• 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

▶️ 출력 조건

• 첫째 줄에 답을 출력한다.

---

풀이

해당 문제는 코드를 작성하는 시간보다 문제를 어떻게 풀지 고민하는 시간이 더 오래걸렸다.

(오답을 2번 정도 받았음...)

처음에는 가장 낮은 무게의 로프에 맞춰서 N 만큼 곱해주면 된다고 생각했다.

따라서 예제의 정답이 20이 나온 이유도 10 * 2 = 20 이라고 생각했다.

 

그러나 추가로 예제를 만들어보니 내 방법이 잘못되었다는 것을 인지했다.

예를 들어 로프가 5개 있는데 각 무게는 2, 4, 7, 9, 10 있다고 가정해보겠다.

중요한 포인트는 "임의로 몇 개의 로프를 골라서 사용해도 된다" 라는 조건이다.

그렇다면 가장 무게가 높은 로프부터 (무게가 높은 로프가 낮은 로프보다 무거운 짐을 들 확률이 높다고 생각했음) 작은 로프 순으로 하나씩 꺼내보며 들 수 있는 최대 중량을 구해보겠다.

 

중량을 계산하는 공식은 가장 낮은 무게 * 총 로프 개수

• 10 뽑았다고 가정 -> 10 * 1 = 10
• 10, 9 뽑았다고 가정 -> 9 * 2 = 18
• 10, 9, 7 뽑았다고 가정 -> 7 * 3 = 21
• 10, 9, 7, 4 뽑았다고 가정 -> 4 * 4 = 16
• 10, 9, 7, 4, 2 뽑았다고 가정 -> 2 * 5 = 10

이렇듯 3개를 뽑았을 경우가 가장 높은 무게를 들 수 있다.

이를 토대로 고안해낸 방법은 모든 경우의 수를 저장해두고 가장 높은 무게를 출력하는 방식으로 구현했다.

 

n = int(input())
ropes = []
for _ in range(n):
    ropes.append(int(input()))

ropes.sort(reverse=True)

count = 1

weight_list = []

for rope in ropes:
    weight_list.append(rope * count)
    count += 1
    
print((max(weight_list)))