[백준-2217]-[그리디알고리즘]-로프

문제링크 : https://www.acmicpc.net/problem/2217

이문제는 병렬로 연결된 로프가 버틸 수 있는 최대 중량이 얼마나 되는지 물어보는 문제이다. 

로프가 한개일 때는 로프가 버틸 수 있는 한계가 최대 중량이다. 

그럼 로프가 두개일 때는?

로프의 최대중량이 작은 로프의 힘 * 2 가 로프가 두개일때 최대 중량이다. 

왜그럴까?? 

문제에 다음 조건이 존재하기 때문이다.

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

중량이 20 일때 로프 두개를 사용하면 한 로프당 걸리는 중량은 10 이다.

최대중량이 10, 12 의 로프 두개가 있을때 최대 중량이 12인 로프가 아무리 10보다 더 들 수 있어도 그 이상의 무게를 들게 되면 최대 중량이 10인 로프는 끊어지게 된다.

w = min( 병렬 연결된 로프의 중량 ) * 병렬 연결된 로프의 수

위의 식을 이용해서 예시로 주어진 10과 15의 로프 두개가 들 수 있는 최대 중량은 10 * 2 가 되므로 20이 된다.

그럼 만약 입력이  아래처럼 된다면 어떻게 될까?

5
35
33
30
20
12

먼저 최대 중량을 저장하는 배열에 정렬을 하여 저장을 한다.

[12, 20, 30, 33, 35] 의 배열이 생성이 된다.

최대중량이 제일 큰 로프순으로 꺼내면서 순서대로 병렬로 연결한다 는 개념으로 계산하면 된다.

1)  중량 35 로프가 꺼내지고 최대 중량은 35

2) 중량 33 로프랑 병렬로 연결 되면서 최대 중량은 66

3) 중량 30 로프가 꺼내지고 먼저 꺼내진 35, 33 로프랑 병렬 연결 되면서 30 * 3 해서 최대 중량은 90

4) 중량 20 로프가 꺼내지고 먼저 꺼내진 35, 33, 30 로프랑 병렬 연결 되면서 20 * 4 해서 최대 중량은 80

5) 중량 12 로프가 꺼내지고 먼저 꺼내진 35, 33, 30, 20 로프랑 병렬 연결 되면서 12 * 5 해서 최대 중량은 60

이중에서 제일 최대 중량이 큰 병렬 연결은 35, 33, 30 로프의 최대 중량 90 이다.

소스

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class B_2217 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int cnt = Integer.parseInt(st.nextToken());
        int arr[] = new int[cnt];
        for(int i=0; i < cnt; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        long max = 0;
        for(int i = cnt-1; i >= 0; i--) {
            arr[i] = arr[i] * (cnt-i);
            if(max < arr[i]) max = arr[i];
        }
        System.out.println(max);
    }
}