[백준] 2217번 로프 (Sort/Greedy)

 

문제

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

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

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

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

 

---

 
처음 문제를 보고 [들어올릴 수 있는 가장 적은 중량 * 로프의 수]로 생각했다.

예제에 있는 10까지 들어올릴 수 있는 로프 a와 15까지 들 수 있는 로프 b가 있을 때 a로프는 10 초과로 들 수 없지만, b는 10을 들 수 있다. 어차피 가장 적은 중량을 들 수 있는 로프의 기준으로 로프 개수를 곱하면 되지 않나 라고 생각했는데 아니었다.

만약 로프가 3개가 있고, 각각 12, 9, 4를 들 수 있을 경우 위 방법으로 풀어보면 최대 중량은 12가 나온다. (4*3)
하지만 이 3개의 로프를 이용해 들 수 있는 최대 중량은 18이다. (9*2)
이 12, 9, 4를 들 수 있는 로프를 각각 a, b, c라고 가정하면 아래와 같다.
12 크기를 들 수 있는 로프는 a 1개 → 12 * 1 = 12
9 크기를 들 수 있는 로프는 a, b 2개 → 9 * 2 = 18
4 크기를 들 수 있는 로프는 a, b, c → 4 * 3 = 12
a와 b 두개의 로프를 이용하여 물건을 들어올리면 주어진 로프로 들 수 있는 최대의 중량이다.
문제에 나와있는 모든 로프를 사용할 필요는 없다는 걸 기억해야 한다.
 

import sys

# N개의 로프
N = int(sys.stdin.readline())

k = []
w = []

for _ in range(N):

    # 로프가 버틸 수 있는 최대 중량
    k.append(int(sys.stdin.readline()))

k.sort(reverse=True)

# 나누어서 들 수 있는 각 중량을 w에 저장
for i in range(N):
    w.append(k[i]*(i+1))

# 최대 중량 출력
print(max(w))

 

#1.
로프가 버틸 수 있는 최대 중량을 각각 k에 입력한다. k = [12, 9, 4]
제일 큰 중량을 들 수 있는 로프는 작은 중량을 당연히 들 수 있으니 내림차순으로 정렬한다. reverse=True

 

#2.
각 물체의 중량과 그 물체를 들 수 있는 로프의 수를 곱해준다.
인덱스 i는 0부터 시작하기 때문에 개수를 곱할 땐 i+1로 곱하여 각 로프가 들 수 있는 중량 w를 구해준다. w = [12, 18, 12]

#3.
max를 이용해 들어올릴 수 있는 각 중량 중 제일 큰 것을 출력해주며 최대 중량을 구할 수 있다.