로프

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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];

        // 로프 정보 저장
        for(int i=0; i<N; i++){
            ropes[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(ropes);

        int max = 0;
        for(int i=0; i<N; i++){
            int weight = ropes[i] * (N-i); // i번째 로프부터 N개 사용
            max = Math.max(max, weight);
        }

        System.out.println(max);
    }
}

그리디를 활용한 문제
k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
예제 1에서 2, 10, 15의 중량을 들 수 있는 로프가 있다고 가정할때
3개의 로프를 모두 사용하면 2kg x 3개 = 6kg 이다.
가장 약한 로프를 10짜리를 선택하면 10kg x 2개 = 20kg이다.
즉, 모든 로프를 다 쓴다고해서 들 수 있는 최대중량이 늘어나는게 아니다.
로프정보를 입력받아 ropes 배열에 저장해준 후, 오름차순 정렬 해준다.
가장 약한 로프 선택을 ropes[i]라고 했을 때, 사용할 수 있는 로프 개수는 (N-i)이다.
for문을 i=0 ~ N-1번 수행하면서 들 수 있는 중량 weight = ropes[i] * (N-i)이고 max값을 비교해나간다.
max값을 출력하면 정답