[백준] 2217번: 로프 자바(Java)

문제

---

2217번: 로프

접근법

---

문제만 이해하면 쉬운 문제다.

k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에 모두 고르게 w/k 만큼의 중량이 걸린다.

N은 이미 입력값으로 주어지고 있기 때문에, 출력값이 W라고 하면 W/N 만큼의 중량이 각 로프에 골고루 걸린다.

즉, N이 2이고, 10, 15가 로프의 가용중량으로 주어지면 2*10 = 20이 최대 중량이 되는 것이다.

∵ W/N = (각 로프의 가용 중량 중 최솟값) / W = (각 로프의 가용 중량 중 최솟값) * N

이때, 문제의 예외가 발생한다.

모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

이 부분이다. 따라서, 우리는 항상 각 로프의 가용 중량 중 최솟값을 고르는게 아니라 최솟값부터 하나씩 없애보면서 로프가 버틸 수 있는 최대 중량을 구해야 하는 것이다.

예를 들어보자.

3 5 10 15가 주어진다고 하면, 10이 최솟값이므로 5 * 3 = 15을 최대 중량으로 구할 수 있다. 하지만 5를 포함하지 않아도 되므로 제거하고 구하면 10 * 2 = 20으로 더 커지는 것을 볼 수 있다. 15 * 1 = 15 보다 20이 더 크기 때문에 답은 20이 된다.

코드를 보면 이해가 빠를 것이다.

 

풀이

---

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> ropes = new ArrayList<>(N);

        for (int i = 0; i < N; i++) {
            ropes.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(ropes);

        int W = 0;

        for (Integer rope : ropes) {
            W = Math.max(W, rope * N);
            N--;
        }

        bw.write(String.valueOf(W));
        bw.flush();
    }
}