[Python | 백준 2217번] 로프

https://www.acmicpc.net/problem/2217

2217번: 로프

 

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

---

내 풀이

처음에 리스트로 받아서 최소값과 리스트 안의 수 k를 곱해서 견딜 수 있는 무게의 최댓값을 갱신해주는 방식으로 풀이를 작성했으나, N이 100,000개까지 가다보니 100,000개를 10만번 반복문을 돌며 min()을 써서 또 추가 연산과정이 들다보니 자연스럽게 시간 초과가 발생했다. 

 

# 시간 초과

N = int(input())
rope = []
for i in range(N):
  rope.append(int(input()))

max_w = 0
for _ in range(N):
  temp = min(rope) * len(rope)
  if temp >= max_w:
    max_w = temp
  rope.remove(min(rope))

print(max_w)

 

 

그래서 초반에 시간이 조금 걸리겠지만 리스트를 먼저 내림차순으로 정렬한 다음에 해당 위치의 값을 최소라고 가정하고 그 값의 위치 값을 k라고 가정하여 계산식을 만들었다. 즉, 리스트는 그대로 두되 자른 것처럼 취급하여 계산하겠다는 것이다. 

 

예를들어 [10, 9, 8] 이 있다고 하면

10이 최소값이라고 가정하면 리스트 길이는 [10] 1개여야 하니 위치값인 1만 곱해서 10* 1 = 10이 최대 중량이 되고,

9가 최소값이라고 가정하면 [10, 9]가 되어 9 * 2 = 18이 최대 중량이 된다. 

마지막으로 8이 최소면 [10, 9, 8]에서 8* 3 = 24가 최대 중량이 되어서

제일 높은 최대 중량인 24가 출력값이 된다. 

 

# 35364kb 3928ms

N = int(input())
rope = []
for i in range(N):
  rope.append(int(input()))

rope.sort(reverse=True)
max_w = 0

for k in range(len(rope)):
  temp = rope[k] * (k+1)
  if temp >= max_w:
    max_w = temp

print(max_w)

 

다행히 시간 초과는 안떴지만 3928ms로 꽤나 시간이 소모되길래 왜그럴까 생각해봤는데

입력을 한 줄씩 처리하고 다 받은 다음에 정렬을해서 그런것 같아서

sys의 readline을 사용해서 한 번에 받은다음에 한 줄 씩 처리했다. 

 

# 35364kb 112ms

import sys
N = int(input())
rope = []
for i in range(N):
  rope.append(int(sys.stdin.readline()))

rope.sort(reverse=True)
max_w = 0

for k in range(len(rope)):
  temp =rope[k] * (k+1)
  if temp >= max_w:
    max_w = temp

print(max_w)

그랬더니 확실히 시간이 줄은 모습을 볼 수 있었다.