백준 2217번 : 로프 java

이 문제는 배열을 내림차순으로 정렬한 후 로프가 들어 올릴 수 있는 물체의 최대 중량을 구하는 알고리즘입니다.

k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때 각각의 로프에는 w/k 만큼의 중량이 걸립니다.

이를 이용하면 가장 버틸 수 있는 중량이 적은 로프 하나가 버틸 수 있는 최대 중량이 L이라고 했을 때 k x L의 중량을 버틸 수 있다는 것을 의미합니다.

위의 예제에서 10 15 두 개의 로프를 이용하여 문제를 풀 때 가장 버틸 수 있는 중량이 적은 로프는 10입니다.

2개의 로프를 이용하였으므로 10 x 2 = 20, 즉 20이 이 2개의 로프를 이용하였을 때 버틸 수 있는 중량의 총량입니다.

이를 이용하여 이 알고리즘을 해결하였습니다.

---

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

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());
        Integer[] valArr = new Integer[N];

        for(int i = 0; i<N; i++)
            valArr[i] = Integer.parseInt(br.readLine());

        Arrays.sort(valArr, new Comparator<>(){
            @Override
            public int compare(Integer a, Integer b){
                return b-a;
            }
        });

        int max = Integer.MIN_VALUE;

        for(int i = 0; i<N; i++)
            max = Math.max(max, (i+1)*valArr[i]);

        System.out.println(max);
    }
}

위에 설명드린대로 버틸 수 있는 중량의 총량을 구했습니다.

내림차순으로 정렬하기 위하여 Comparator을 이용하였습니다.