[Java] 백준 2217 - 로프

 

문제

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

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

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

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

예제 입력

2
10
15

예제 출력

20

 

---

시나리오

로프를 선택적으로 골라서 무게가 w인 물체를 들어올린다고 했을 때 들어올릴 수 있는 최대 무게를 구하는 문제이다.

10, 15의 무게를 견딜 수 있는 로프를 모두 사용해 물체를 들어올리면 무게의 최대 무게는 20이 된다.

문제의 조건대로 계산했을 때 '사용하는 로프 중 무게 한도가 가장 낮은 로프 * 로프의 개수'가 버틸 수 있는 최대 무게가 되기 때문이다. 

 

그렇다면 10, 15, 30, 33, 35의 무게를 견딜 수 있는 로프가 주어졌을 때 정답을 계산해보자.

모든 로프를 사용한다고 하면 10(한도가 가장 낮은 로프) * 5(로프의 개수) = 50이 버틸 수 있는 최대 무게가 된다.

15부터 모든 로프를 사용한다고 하면 15 * 4 = 60,

30부터 모든 로프를 사용한다고 하면 30 * 3 = 90,

33부터 모든 로프를 사용한다고 하면 33 * 2 = 66,

35만 사용한다고 하면 35 * 1 = 35가 되므로 30부터 모든 로프를 사용하는 게 정답이 된다.

 

이를 일반화해 문제를 풀면

1. 로프를 리스트(배열)로 입력받는다.
2. 오름차순 정렬한다.
3. 첫번째 요소부터 끝까지 돌며 '현재 요소의 하중 * (전체 로프 개수  - 현재 요소의 인덱스)'를 계산한다.
4. 위 결과값과 이전에 계산한 결과값의 최댓값 중 최댓값을 저장한다.
5. 저장한 최댓값 출력

의 과정을 거치게 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        int maxWeight = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<Integer> rope = new ArrayList<>();

        //1.입력
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int ln = Integer.parseInt(br.readLine());
            rope.add(ln);
        }
        //2. 정렬
        Collections.sort(rope);

        //3. 반복
        for (int i = 0; i < N; i++) {
            maxWeight = Math.max(rope.get(i) * (N - i), maxWeight);
        }
        System.out.println(maxWeight);
    }


}