문제

[요약]

• N개의 로프
• k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 w/k 만큼의 중량이 걸림
• 들어올릴 수 있는 물체의 최대 중량을 구해라

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

풀이

문제의 조건 중 k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때 각각의 로프에 w/k 만큼의 중량이 걸린다는 점을 이해하는 것이 우선이다.
이 부분에서 살짝 이해가 안 됐다.

주어진 예제를 보면 10은 로프가 하나일 때 버틸 수 있는 최대 중량이고 15 역시 최대 중량이다.

그러면 로프 2개일 때는 어떨까? 20이 최대 중량이 된다.

이유는 w/k 라는 조건을 잘 보자.

중량이 20이고 2개의 로프이니까 20/2 = 10 즉, 하나의 로프에 걸리는 중량이 10이다. 다른 하나가 15의 무게까지 물체를 들어올릴 수 있다고 해도 다른 하나 10짜리 로프가 버틸 수 없는 것이다.

결론은 최대중량(w)은 연결되는 로프의 중량의 최솟값에 연결되는 로프의 수를 곱하면 되는 것이다.

최대중량(W) = min(연결된 로프 중량) * 로프의 수

따라서 주어진 로프 중량을 내림차순으로 정렬한 뒤 제일 큰 로프 중량부터 병렬로 연결하여 구하면 된다.

코드

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		ArrayList<Integer> al = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			al.add(sc.nextInt());
		}
		
		// 내림차순
		Collections.sort(al, Comparator.reverseOrder());
		
		int result = 0;  // 최대 중량
		
		for(int i = 0; i< n; i++) {
			int w = al.get(i) * (i+1);
			if(result < w) {
				result = w;
			}
		}
		System.out.println(result);
			
	}
}