[백준] Greedy: 로프

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

문제 접근

각 로프가 주어질 때, 최대로 버틸 수 있는 무게를 찾아야 한다.

처음에는 가장 작은 무게가 N개 있으면 될 것 같았다.

하지만 가장 허용 중량이 큰 로프의 허용 중량이 다른 로프들 보다 매우 차이가 난다면 이는 적용될 수 없다.

그렇다면 여러 로프가 주어졌을 때 가장 큰 무게를 지탱할 수 있도록 선택하는 방법은 어떤 것일까?

우선은 가장 큰 무게를 지탱이 가능한 로프를 선택해야 할 필요가 있다.

그렇다면 현재 모든 로프를 사용할 경우 min중량 * 개수 이다.

하지만 이 때 지탱 무게가 작은 로프가 낀다면 전체 허용 중량이 작아지게 된다. 

여기서 가장 작은 무게를 지탱하는 로프를 하나 씩 제거해서 Max값을 비교해 보자.

즉, 순차적으로 가장 작은 무게를 하나 씩 제거해서 비교를 하다보면 점차 전체 허용중량이 증가할 것이다.

루프를 돌면서 최대 값을 찾으면 된다.

 

해결 코드

package baekjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class _2217 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];
        for (int i=0; i<N; i++){
            int c = Integer.parseInt(br.readLine());
           numbers[i] = c;
        }

        int max = 0;
        Arrays.sort(numbers);

        for (int i=0; i<N; i++){

            max = Math.max(max,numbers[i] * (N-i));
        }

        System.out.println(max);


    }
}