[BOJ] 백준 2217번 : 로프 (JAVA)

문제

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

 

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

 

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

 

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

 

 

출력

첫째 줄에 답을 출력한다.

 

 

풀이

그리디 알고리즘을 활용하여 풀 수 있는 문제였습니다.

 

문제에서는 몇 개의 로프를 사용하여 로프가 버틸 수 있는 최대 용량을 구하라고 하였습니다.

예를 들어, 10과 15 무게를 지탱할 수 있는 로프가 있다고 가정해 봅시다.

 

15 로프만 사용할 경우 15의 무게를, 10 로프만 사용할 경우 10의 무게를 지탱할 수 있습니다.

하지만, 1개가 아니라 여러 개의 로프를 사용할 경우에는 이야기가 달라집니다.

 

예를 들어, 10 로프와 15 로프를 동시에 사용한다고 하면, 최대 무게 w는 20입니다.

만약, w가 20보다 큰 21이라고 가정하면, 각각의 로프에 대해서 10.5의 무게가 실리기때문에 10 로프는 이를 지탱할 수 없습니다.

 

위의 내용을 이해했다면, 이제 식을 일반화해 봅시다.

특정 로프를 사용할 경우, 그 로프보다 무게가 큰 로프를 모두 이용하는 것이 이득입니다.

즉, 최대 무게 w는 rope[k] * (N - k)라는 식이 나오게 됩니다. (로프를 오름차순 정렬했다고 가정.)

 

 

따라서, 우리가 할 일은 로프의 무게를 오름차순으로 정렬한 후, 위 식을 사용하여 최댓값을 반환하면 끝입니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.