https://www.acmicpc.net/problem/2217
시간 2초, 메모리 192MB
input :
-
N (1 <= N <= 100,000)
-
최대 중량 KG (1 <= KG <= 10,000)
output : -
들어올릴 수 있는 최대 중량 구하기.
조건 : -
K 개의 로프로 중량 W 인 물체 들 때 -> 로프에 W / K 만큼의 중량이 걸림.
-
모든 로프 사용 X, 몇 개의 로프 고르기 가능.
여러개의 로프로 물체를 들면.
각 로프 마다 W / K 중량이 걸리고 그 로프가 K개 존재함.
만약 현재가 N 이라면, N - 1번째의 최댓값을 가지고 있는 total.
시작부터 N - 1번째 까지의 합을 가지고 있는 prev.
로프의 개수를 세아리는 cnt.
현재 로프의 최대 중량을 나타내는 cur.
모두 동일한 하중을 받는다는 의미.
각 로프의 최대 중량을 넘을수 없다와 동일.
내림차순 정렬을 통해 가장 큰 것 부터 생각을 한다.
여러개의 로프를 쓸 경우엔
가장 작은 중량 * 로프의 개수 이것을 내림차순 정렬을 했을 때 구하기 쉽다.
2개의 로프를 쓸 때 가장 큰 경우.
3개의 로프를 쓸 때 가장 큰 경우. 를 생각해보면 내림차순 정렬이 필요하다.
import sys
N = int(sys.stdin.readline())
KG = [0] * (N)
for i in range(N):
data = int(sys.stdin.readline())
KG[i] = data
KG.sort(reverse=True)
total = 0
for idx in range(len(KG)):
num = idx + 1
total = max(total, KG[idx] * num)
print(total)
시작할때 동일한 하중이란 것을 생각하지 못해서 시간을 허비함.
