[백준] 2217번 > 로프

www.acmicpc.net/problem/2217

2217번: 로프

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1

2

10

15

예제 출력 1

20

 

---

풀이

처음에는 로프의 중량을 정렬하고 젤 작은 값에다 개수를 곱하면 최대 중량일 것이라 생각했다.

(나머지는 다 rope[0]이상이니까) 

하지만 반례가 있었다. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

예를 들어, [1, 10, 12, 13] 이 있다면 첫번째 로프를 빼고 나머지끼리 계산하는게 더 크기때문이다.

import sys
n = int(input())
rope = sorted([int(sys.stdin.readline().strip()) for _ in range(n)])
weight_list = []
for i in range(n):
    weight_list.append(n*rope[i])
    n -= 1
print(max(weight_list))

따라서 내가 선택한 방식은 n개부터 1개 로프를 선택하는 경우를 다 구한 후, max값을 구했다.