[Baekjoon Online Judge] 2217번: 로프

2217번: 로프

2217번: 로프

 n개의 로프를 활용해서 가장 무거운 중량을 구하는 문제이다. 여기서 고려해야 하는 요구사항은 k개의 로프를 사용하여 중량 w인 물체를 들어올리면, 각각의 로프는 모두 고르게 w/k 만큼 중량이 걸리게 된다. 각각의 로프는 자신이 버틸 수 있는 중량 이상을 버틸 수 없다. 마지막으로 로프는 전부 사용하지 않아도 된다.

 

 로프를 전부 사용하지 않아도 되기 때문에 로프를 중량 내림차순으로 정렬시킨다. 버틸 수 있는 무게가 큰 순서부터 로프를 추가 시켜서 가장 큰 무게를 버틸 수 있는 max 값을 계산한다.

 

예시

 

5
8
7
5
1
2

 

 5개의 로프를 입력 받았고, 각각이 버틸 수 있는 중량은 8, 7, 5, 1, 2이다. 이것을 내림차순 정렬하면, 8,7,5,2,1이다.

 만약 로프를 한개만 사용할 때 최대 중량은 8이다. 로프를 두개 사용한다면, 7 x 2 = 14를 버틸 수 있다. 두번째 로프의 경우 7 이상의 무게를 버틸 수 없기 때문이다. 로프를 세개 사용한다면, 5 x 3 = 15가 된다. 로프를 네 개 사용한다면 2 x 4 = 8이 된다. 결국 로프가 가장 버틸 수 있는 15가 되는 것이다.

 

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

public class Baekjoon2217 {

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine()); // 로프의 개수
        Integer[] ropes = new Integer[n]; // 각 로프들이 버틸 수 있는 중량 모음

        for (int i = 0; i < ropes.length; i++) {
            ropes[i] = Integer.parseInt(bufferedReader.readLine());
        }

        Arrays.sort(ropes, Collections.reverseOrder()); // 내림차순 정렬

        int max = 0;
        for (int i = 0; i < ropes.length; i++) {
            if (max < ropes[i] * (i + 1)) { // 이전 최대값 보다 로프를 늘렸을 때 최대값이 더 크면
                max = ropes[i] * (i + 1);
            }
        }

        bufferedWriter.write(String.valueOf(max));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}