백준 문제풀이 - 2217번

이형래·2022년 6월 30일
0

백준문제풀이

목록 보기
21/36

백준 문제풀이 - 2217 번


링크 -> https://www.acmicpc.net/problem/2217


1. 요약 및 풀이방법

여러개의 로프를 이용하여 들어올릴 수 있는 최대 하중을 구하는 문제입니다.

중량 ww인 물체를 매달면 각 kk개의 로프에 w/kw/k의 하중이 동일하게 걸리기 때문에,
가장 약한 로프가 버틸 수 있는 무게를 기준으로, 사용한 로프의 수를 곱해주면 견딜 수 있는 총 무게를 구할 수 있습니다.
로프가 10개 있을때, 첫번째 로프는 10kg, 나머지 9개의 로프는 100kg을 버틸 수 있다고 하면,
로프 10개를 다 쓰면 10kg * 10 = 100kg 의 무게를 버틸 수 있지만,
첫번째 로프를 제외하면 100kg * 9 = 900kg 의 무게를 버틸 수 있습니다.

이렇게 굳이 로프를 전부 사용하는게 좋은것은 아니기 때문에,
약한 로프부터 제외하면서 무게를 측정하면 해결할 수 있습니다.


2. Code

import sys

def main():
    N = int(input())
    weights = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
    weights.sort()

    max_weight = 0
    for weight in weights:
        max_weight = max(max_weight, weight*N)
        N -= 1
    print(max_weight)

if __name__ == "__main__":
    main()

3. 학습 내용

일반적인 그리디 알고리즘 문제로,
로프가 견딜 수 있는 하중을 오름차순으로 정렬하여 해결합니다.


4. 결과

profile
머신러닝을 공부하고 있습니다. 특히 비전 분야에 관심이 많습니다.

0개의 댓글