[백준/Java] 2217번 - 로프

🙂 문제

2217번: 로프

💡풀이

N개의 로프가 주어졌을 떄 들어올릴 수 있는 물체의 최대 중량을 구해야 한다.
예제 입력을 살펴보자. 각각 버틸 수 있는 최대 중량이 10, 15인 로프 2개인 경우에 들어올릴 수 있는최대 중량을 구해야 한다.

15 * 2 = 30  
10 * 2 = 20 

중량이 30인 경우에는 각각의 로프에 15(= 30 / 2)만큼의 중량이 걸리게 되고 10짜리 로프는 견디지 못하기 때문에 2개의 로프로 들어올릴 수 있는 최대 중량은 20이다.

❗ 식을 세우기 위해 다른 경우를 보자. 10, 20, 25, 40 로프 4개인 경우는 어떨까? 꼭 모든 로프를 사용할 필요는 없다. 가능한 최대 중량은 다음과 같다.

4개 - 10 * 4 = 40     ---> ropes[0] * (4 - 0) 
3개 - 20 * 3 = 60     ---> ropes[1] * (4 - 1) 
2개 - 25 * 2 = 50     ---> ropes[2] * (4 - 2)
...

3개를 이용하는 경우 25 * 3 은 20짜리가 견디지 못하기 때문에 불가능하고
2개를 이용하는 경우는 45 * 2는 25짜리가 견디지 못한다.

따라서 이 경우에는 최대 중량인 60이 출력되야 할 것이다.

로프의 중량을 오름차순으로 나열했을때 가장 작은 중량 x 로프의 개수 부터 시작해서 차례로 비교해서 가장 큰 값을 찾아내면 된다.

💻답안

import java.io.*;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] ropes = new int[n];
        int res = 0;

        for (int i = 0; i < n; i++) {
            ropes[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(ropes);
        res = ropes[0] * n;

        for (int i = 1; i < n; i++) {
            if (ropes[i] * (n - i) > res) {
                res = ropes[i] * (n - i);
            }
        }

        System.out.println(res);
    }
}

---

👩‍💻 생각

그리디 알고리즘은 사실 어떤 개념이 존재한다기보다는 정확한 답을 찾기 위한 탐욕적 접근법이기 때문에 내가 풀이한 방법이 정당한지 검토하는 과정이 중요하다. 하지만 가장 중요한 부분은 역시 스스로 고민해서 어떻게든 답을 찾을 수 있는 해법을 찾을 수 있는 것이라고 생각한다.
이 문제같은 경우는 간단한 문제라서 비교적 짧은 시간에 해결법을 찾을 수 있었다. 앞으로 다양한 문제를 접하면서 깊게 생각하는 능력을 키워야 겠다.😊