[BOJ] 2217 로프

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다

 

 

처음엔 갈피를 못찾을 수 있으나 조금만 생각하면 아이디어가 떠오른다.

"엥? 그럼 제일 약한 로프*n하면 최대값 아닌가?"라고 생각할 수 있다.

하지만 "모든 로프를 사용하지 않아도 된다"가 핵심이다.

2

10

100

인 경우, 정답은 100이다. 1개의 로프만 사용하면 되기 떄문이다.

 

즉, 정렬후에 가장 큰 로프부터 차례로 내려오면서

지금까지의 최대값 vs 현재로프를 i+1개 사용했을때의 무게 를 비교하기만 하면된다.

 

5

1

2

3

4

5

인 경우

5부터 순회한다.

m = max(5, 5*1) => 5

m = max(m, 4*2) => 8

m = max(m, 3*3) => 9

m = max(m, 2*4) => 9

m = max(m, 1*5) => 9

 

정답은 9

 

반례를 보고 아이디어를 유추해 맞춰서 뿌듯했다.

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())

# 모든 로프를 사용할 필요가 없다.
ropes = []
for _ in range(n):
    ropes.append(int(input().rstrip()))

# 역순정렬
ropes = sorted(ropes, reverse=True)
m = 0
for i in range(n):
    # 1개선택 or 지금까지 로프만 선택
    m = max(m, ropes[i]*(i+1))

print(m)