[그리디 알고리즘] 2217번 - 로프

[백준] 2217번 - 로프

1) 문제 해결 아이디어

물체의 최대 중량을 구하기 위해 로프를 내림차순 정렬하는 것이 포인트다.

 

물체의 중량이 w, 로프가 n개 일 때 각 로프에 걸리는 중량은 w/n 이다.

즉, 물체의 중량 = n * 로프 중량

 

모든 로프를 사용해야할 필요는 없으므로 로프는 (1 ~ n) 개 사용할 수 있다.

반복문을 통해 줄의 개수 n개에 따른 물체의 중량값을 게산하여 리스트에 덮어쓴다.

여기서 반복문 인덱스는 0부터 시작하므로 실제로 곱해주는 값은 (i +1) 이어야 함을 주의한다.

해당 리스트의 최대값을 max() 함수로 구한다.

 

2) 소스코드

n = int(input())  # 줄 개수
powers = [int(input()) for _ in range(n)]  # 각 줄의 최대 중량
powers.sort(reverse = True)

for i in range(n):
  powers[i] *= (i + 1)
print(max(powers))