테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 로프 ======

===== 풀이 =====
  * k개의 로프를 썼을때 각각의 로프에 걸리는 중량은 동일하다. 그말은 k개의 로프를 쓸 경우에는 가장 강한 로프 k개를 쓰는것이 최적이라는 뜻이고, 이때 들수 있는 중량은 k번째로 강한 로프에 의해서 결정되다는 뜻이다.
  * 따라서, 전체에서 i번째로 강한 로프가 i개 있을때 들수 있는 중량 W[i]를 모든 i에 대해서 계산한 다음에 max(W)를 구하면 끝이다. i번째로 강한 로프를 바로 찾는 것은, 그냥 로프들을 정렬한 다음에 순회하면 된다. 그럼면 정렬에 O(nlogn), 나머지에 O(n)이 걸리므로 총 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2217. 로프".

- Problem link: https://www.acmicpc.net/problem/2217
- Solution link: http://www.teferi.net/ps/problems/boj/2217
"""

import sys


def main():
    N = int(sys.stdin.readline())
    ropes = [int(sys.stdin.readline()) for _ in range(N)]

    ropes.sort(reverse=True)
    print(max(rope * i for i, rope in enumerate(ropes, start=1)))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_4}}