사용자 도구

사이트 도구


ps:problems:boj:2217

로프

ps
링크acmicpc.net/…
출처BOJ
문제 번호2217
문제명로프
레벨실버 4
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어Python
제출기록33052KB / 132ms
최고기록92ms
해결날짜2021/12/30

풀이

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

코드

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

토론

댓글을 입력하세요:
N X I A Z
 
ps/problems/boj/2217.txt · 마지막으로 수정됨: 2021/12/31 17:24 저자 teferi