Greedy(5)_로프(2217번)

작성일 | In

백준 2217

로프문제 첫번 째 줄에 로프의 개수 N이 주어지고 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다.

문제 이해하기 예시 코드를 보면 로프가 2개가 주어졌고, 각각 10과 15의 물체를 들어올릴 수 있다. 얼핏 보면 최대 중량이 10 +15/2를 한, 12.5를 들어올릴 수 있을 것 같지만, 한 로프가 최대 중량이 10이었으므로 결과적으로 10만큼을 들어올릴 수 있기에 10*2를 한 20이 답이 된 것이다.

따라서 배열로 로프를 담은 뒤, 최대 하중이 가장 작은 값 곱하기 밧줄의 개수를 통해 최대 중량을 찾아줘야 한다. 이를 만족하기 위해서는, 정렬을 할 필요가 있겠다.

예를 들어 [35,33,30,20,12,5]가 있다고 하면, 제일 큰 로프순으로 꺼내면서 순서대로 병렬로 연결한다는 개념으로 계산하면 된다

  1. 중량이 35인 로프 꺼내고 35
  2. 중량이 33인 로프 꺼내고 33 * 2
  3. 중량이 30인 로프 꺼내고 30 * 3 이런 식이다.

아이디어

배열에 담아서 리버스해서 하나씩 꺼내면서 가장 큰 값 출력

import sys

N = int(sys.stdin.readline())

arr = []
for i in range(N):
    arr.append(int(sys.stdin.readline()))
arr.sort(reverse=True)

max = 0
for i in range(N):
    arr[i] = arr[i]*(i+1)
    if(max < arr[i]):
        max = arr[i]
print(max)

참고자료

[문제 이해에 도움을 준 블로그]https://pangsblog.tistory.com/21

0%