백준 2217번: 로프 (JAVA)

 

문제 해석

 

N개의 로프가 주어지고 각 로프가 견딜 수 있는 최대 중량이 주어진다.

k개의 로프로 중량이 w인 물체를 들어올릴 때 각 로프에게 전달되는 중량은 w/k 이다.

주어진 로프들을 자유롭게 이용하여 들어올릴 수 있는 최대 중량을 구해야 한다.

 

알고리즘

 

로프 사용이 강제적이지 않기 때문에 사용할 수 있는 로프 쌍을 만들어 큰 값만 남아있도록 해야 한다. 

하지만 이 문제에서 k개의 로프로 중량이 w인 물체를 들어올릴 때 각 로프에게 전달되는 중량은 w/k 이다.

1과 25과 100을 칠 수 있는 세 로프가 있을 때

세 로프를 모두 사용한다면 가능한 최대 중량은 2

두 로프를 사용한다면 가능한 최대 중량은 50

한 로프만 사용한다면 가능한 최대 중량은 100이다.

따라서 모든 로프 쌍을 만들 필요 없이 가장 중량을 잘 치는 로프 하나를 사용하는 것부터 시작하여

로프를 하나씩 내림차순으로 추가해가면서 칠 수 있는 중량의 최댓값을 갱신해주면 된다.

각 로프가 칠 수 있는 중량을 저장하는 배열을 만들고 정렬한 뒤 큰 값부터 꺼내 사용하는 로프 개수와 곱해주며

그 값을 이용해 최댓값을 갱신한다.

-> 현재 칠 수 있는 중량 = (꺼낸 로프가 칠 수 있는 중량) x (사용하는 총 로프 수)  

 

코드