[백준] 로프 (BufferedReader, Array.sort(), greedy 그리디 알고리즘, 2217번, Java)

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량을 구하는 문제입니다.

 

이 문제에서 중요한 것은 각 로프가 들 수 있는 중량을 기준으로, 여러 로프를 함께 사용하여 최대로 들 수 있는 중량을 계산하는 것입니다.

 

먼저 빠른 입력을 위해서 BufferedReader 클래스를 사용하여 입력을 받아주고, 각 로프를 rope배열에 넣어줍니다.

 

이 때 각 로프에 대해 해당 로프를 포함하여 그보다 강한 모든 로프들이 버틸 수 있는 최대 중량을 계산하는 것이 효과적입니다.

로프를 중량이 높은 순서대로 정렬하면, 각 로프를 포함하여 그보다 강한 로프들이 함께 버틸 수 있는 최대 중량을 쉽게 계산할 수 있다는 점입니다.

 

따라서 먼저 정렬을 해줘야합니다. 또한 오름차순으로 정렬을 했다는 기준에 rope[k] * (N - k)라는 점화식이 나오게 됩니다.

 

내림차순일 경우 arr [i] * (i+1)

 

입력이 4 30, 20, 25, 10으로 주어진다면 [10,20,25,30]으로 정렬이 됩니다.

 

 

30kg로프만 연결되어 있다면 최대 중량은 30 * 1 ➡️ 30kg입니다.

이 때 다음 큰 로프인 25kg를 병렬로 결합한다면 최대 중량은 25 * 2 ➡️ 두 로프와 함께 50kg를 버틸 수 있습니다.

그다음 큰 중량인 20kg를 결합한다면 최대 중량은 20 * 3 ➡️세 로프와 함께 60kg를 버틸 수 있습니다.

마지막 10kg를 결합한다면 최대 중량은 10 * 4 ➡️ 네 로프와 함께 40kg를 버틸 수 있습니다.

 

이 중 최대로 버틸 수 있는 중량은 30,25,20이 병렬로 결합된 60이 됩니다.

 

---

가장 작은 무게를 버티는 로프 * 병렬 연결된 로프들의 수 ❓

로프들이 병렬로 연결되어 있을 때, 병렬로 연결된 로프들은 각각 동일한 중량을 버틸 수 있습니다.

 

따라서 병렬 연결된 로프들의 중량은 모두 동일해야 합니다.

 

그리고 병렬 연결된 로프들은 각각 동일한 중량을 버틸 수 있으므로, 이 중량들 중 가장 작은 값이 전체 병렬 연결된 로프들의 중량입니다.

 

이때 "이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성"이라고 했으니 1개~N개 로프들을 연결했을 때 가장 많은 무게를 버틸 수 있는 중량을 구하면 됩니다.

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기