문제
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
생각의 흐름
이 문제를 풀 때, 임의의 몇개의 로프를 골라서 사용해도 된다는 부분이 있어서 고민을 많이 했다.
우선 여러개의 로프를 이용하면 무조건 고르게 w/k로 나눠지니까 로프가 버틸 수 있는 최대 중량이 최소인 로프에 맞춰서 무게를 들어야한다는 점을 생각했다. 임의의 몇개의 로프를 고르는 개수는 1부터 받은 로프의 수 n까지 전체를 봐야한다고 생각해서, 반복문을 역순으로 돌면서 고른 수 중에서 최소값을 찾아 그 최솟값과 고른 로프 수를 곱한 것을 배열에 넣어 배열에서의 최댓값을 찾아내는 방식으로 구현했다.
코드
import sys
n = int(input())
arr = []
w_arr = []
for _ in range(n):
arr.append(int(sys.stdin.readline()))
for i in range(n,0,-1):
m = min(arr)
w_arr.append(i*m)
arr.remove(m)
print(max(w_arr)) 개선할 점
파이썬에는 sort()가 있다는 걸 잊고 있었어서,
반복문을 돌때마다 remove를 써주고, 최솟값을 또 찾아주는 방식을 사용했는데, min()도 O(N)이 걸리고, remove()도 O(N)이 걸려서 시간이 오래 걸린다.
sort() 함수로 처음부터 정렬해서 찾아내는 코드로 수정해서 작성해봐야할 것 같다.
추가적으로 다른 사람이 짧게 짠 코드를 참고해보니
n,*l=map(int,open(0))
l.sort()
print(max(l[i]*(n-i) for i in range(n)))open(0)을 이용해서 입력을 받는 부분과
내포함수로 바꿔서 짜는 것을 공부해봐야할 것 같다.
