[백준] 2217번 : 로프 (파이썬)

문제

나의 답안

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))

접근방법

• k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다 라는 조건에 따라 작은 중량을 드는 로프가 최대 무게를 결정함을 알 수 있다.
• 10의 로프는 15만큼의 중량을 버틸 수 없기 때문이다.
• 따라서 최소 중량을 드는 로프 * 연결하는 로프의 수 로 최대 중량을 구할 수 있다.

1. sort로 로프의 무게를 내림차순으로 정렬해준다.
   내림차순으로 정렬하는 이유는 최대 중량을 구하기 위해서이다.
   [100,50] 일 때, 첫번째 로프는 혼자 100의 무게를 버틸 수 있다. 그러나 두번째 로프는 100의 무게를 견딜 수 없으므로 최대 중량은 50, 100은 50을 버틸 수 있으므로 최대 중량은 100이 되면서, 각 로프가 감당하는 중량을 나눌 수 있다.
   따라서 최적의 해를 구하기 위해 내림차순으로 정렬할 필요가 있다.
2. 이후 n번 반복을 통해 최소 중량을 드는 로프 * 연결하는 로프를 구해주고 이를 배열에 추가해준다.
3. 마지막으로 max로 result배열의 최댓값(최대 중량)을 구해주고 출력해준다.