[백준 2217] 로프 - Python (그리디 알고리즘, 정렬)

 

2217번: 로프

 

 

<내 코드>

 

N = int(input())

weights = [int(input()) for _ in range(N)]
weights.sort(reverse=True)  # 내림차순


for i in range(N):
    weights[i] = weights[i] * (i+1)

print(max(weights))

 

 

문제 접근 방법

- 로프를 병렬로 연결하면 각 로프에는 w/k만큼의 동일한 중량이 걸린다.

- 즉, 가장 작은 무게를 들 수 있는 로프가 들 수 있는 질량 * 병렬연결 로프 개수 = 최종 무게

- 가장 무거운 무게를 들 수 있는 로프부터 내림차순으로 정렬한다.

 

처음에는 너무 어렵게 접근해서 복잡하게 생각했다. 그래서 디큐를 활용해 하나씩 빼고 넣고 하려고 했다가 실패했다. 이렇게 단순하게 풀릴지는... 후..