백준 No.2217 로프 - JAVA

 

문제

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

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

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

 

2
10
15

 

 

풀이

- 처음에 로프의 제일 작은 값으로 하려 했다. 그러면 모두 무게를 나눠가지며 할 수 있기 때문에 그렇게 하려했지만 최댓값이 아니다. 

- 그래서 하나씩 해당 로프 기준으로 무게를 나눴을 때 많은 무게를 들 수 있는지 체크해야한다. 10, 15가 주어질 때를 예로 들면

- 이 상황에서 15키로 한 개만 사용해서 들 경우 -> 15키로만 들 수 있다. -> 10키로일 경우 10키로는 15키로를 감당하는 로프도 들 수 있기에 최대 20키로까지 들 수 있다. 

- 위에 방법대로 살펴보면 로프 무게를 배열로 받아서 배열을 내림차순으로 정렬하고, 정렬한 배열을 값을 하나씩 처음부터 꺼내는데 제일 높은 값부터 arr[i] * (i+1)  --> 해당 로프만 견딜 수 있는 무게로 할 때로 구하면 된다. 즉 가장 큰 값만 들 수 있는 로프를 사용하면 가장 쎈 로프만 사용할 수 있다. 이렇게 값을 구하면서 점차 가장 큰 값을 구해나간다.

- 가장 튼튼한 로프 쓸 때 , 다음 로프랑 같이 쓸떄 (대신 감당할 수 있는 무게가 줄어듬 하지만 로프 개수는 증가)  를 계속 비교해가면서 가장 큰 값을 찾는다.

 

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

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   //로프 개수

        Integer arr[] = new Integer[N];

        for(int i=0;i<N;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr, Collections.reverseOrder());
        int MAX =0;
        for(int i =0;i<arr.length;i++){

            int temp = arr[i] * (i+1);  //20


            if(MAX < temp){ //
                MAX = temp; //20
            }
        }
        System.out.println(MAX);
    }
}