Baekjoon_2217_로프

문제 설명

• 로프 N개
• k개의 로프로 w중량의 물체를 들어올릴 때 한 로프에 가해지는 무게는 w/k

=> 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량 출력

 

문제 풀이

로프를 이용해 들 수 있는 최대 중량을 구하려면 로프가 들 수 있는 무게는 크면서, 로프가 많아 무게를 최대한 나눠가져야 한다.

 

로프 3개가 버틸 수 있는 질량이 100, 100, 100 이라고 하면 중량 x의 물체가 한 로프 당 x/3씩 가해진다. 각각의 로프는 100씩 버틸 수 있으므로 이 로프들이 들 수 있는 물체의 최대 중량은 300이다.

 

하지만 로프 3개가 버틸 수 있는 질량이 100, 100, 10 이라고 하면 세번째 로프가 10밖에 버티지 못하기 때문에 중량 30의 물체가 최대 중량이 된다.

 

따라서 로프를 a개 고르고 로프 중 가장 적은 무게를 들 수 있는 로프의 최대 중량이 b일 때, 이 로프들이 들 수 있는 무게의 최대는 a x b 이다.

 

이를 이용해 우선순위 큐에 로프의 최대 중량 값을 입력받고, 가장 중량 값이 적은 로프부터 (로프의 무게 x 로프의 개수)를 연산하고, 그 중 최대 값을 찾아 출력했다.

 

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class _2217_로프 {
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i  =0; i<N;++i) {
			pq.add(Integer.parseInt(in.readLine()));
		}
		
		int max = 0;
		while(!pq.isEmpty()) {
			max = Math.max(max, pq.poll() * (pq.size()+1));
		}
		System.out.println(max);
	}
}