백준 2217 - 파이썬

문제를 정리해보면 N(1 ≤ N ≤ 100,000)개의 로프 중에서 여러 개의 로프를 병렬로 연결하면 각 로프마다 고르게 무게가 분포되어 중량을 들 수 있다. 여기서 중량의 최대치를 구하면 되는 문제이다.

 

ex)

23  27  15  11  3

이렇게 로프가 존재할 때 들 수 있는 중량의 무게는 23  46  45  44  15 이렇게 된다. 따라서 최대치는 46이다.

 

문제풀이

처음에 생각해낸 방법은 파이썬의 슬라이싱 기법을 활용하여 푸는 것이었다.

n = int(input())

arr = []

for i in range(n):
    arr.append(int(input()))
    
max_weight = 0
for i in range(len(arr)):
    min_rope = min(arr[:i+1])
    weight = min_rope * (i+1)
    
    max_weight = max(max_weight, weight)
    
print(max_weight)

그런데 이렇게 했을 경우에는 시간 초과가 떴다

계속 고민하며 시간을 줄여 보려 했지만 쉽진 않았고 다른 사람의 코드를 참고해 봤다.

n=int(input())
arr=[]
result=[]
for i in range(n):
    arr.append(int(input()))
    
arr.sort(reverse=True)
         
for i in range(n):
    result.append(arr[i]*(i+1))
    
print(max(result))

이 사람의 풀이는 반복문이 지날수록 가장 작은 무게를 들 수 있는 로프를 사용하게 되니 정렬을 역순으로 저장하여 푼 문제이다.

 

이렇듯 좀 더 효율적인 방법이 존재했다. 좀 더 연습해야겠다.