[BOJ] 2217 로프 (Java)

https://www.acmicpc.net/problem/2217

 

각 각의 로프의 최대 중량이 주어지고, n개의 로프를 병렬로 이용하면 물체 무게를 n빵해서 들어올릴 수 있다.

주어진 예제로 생각해 보자면, 15 로프를 이용하면 최대 15까지 들 수 있지만 10 로프를 함께 이용하면 최소 중량인 10의 2배(로프가 2개니까)까지 들 수 있다.

그럼 10과 15 로프를 병렬로 이용하는 게 최선이다.

만약, 주어진 로프가 5와 20 이라면 20 로프 하나로 20을 들 수 있고, 5 로프를 함께 이용하면 5*2=10밖에 들지 못한다.

따라서 20로프를 하나만 이용하는 게 최선이다.

이를 통해, 우선 병렬보다는 최대 중량의 로프 1개를 이용할 때를 확인해보는 게 우선순위라는 것을 알 수 있고, 그 뒤로는 n빵일 때를 차례대로 계산해봐야한다는 걸 알 수 있다.

즉, 로프가 들어 있는 arr배열을 정렬해서, 로프가 감당 가능한 최대중량일 때부터 물체의 무게를 최댓값으로 갱신하면 된다.

 

<제출 코드>

package BOJ.Greedy;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_2217_로프 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int min = Integer.MAX_VALUE;
        int ans = 0;
        for(int i=n-1; i>=0; i--){
            min = Math.min(min, arr[i]);
            ans = Math.max(ans, min*(n-i));
        }
        System.out.println(ans);
    }
}