Greedy 백준 알고리즘 자바 2217 ‘로프’ 문제풀이

Problem

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다.

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

Output
첫째 줄에 답을 출력한다.

Solution

그리디는 아무래도 아이디어 싸움인 듯하다. 완전히 단순해 보였지만, 모든 로프를 꼭 사용하지 않아도 되기때문에 이 부분에 유의해야 한다. 로프를 1개 선택했을 때의 최대값과 2개를 선택했을 때의 값(여기서는 최대값이 되면 안 된다. 왜냐하면 2개 중 가장 적게 들 수 있는 로프의 기준에 맞춰야 하기 때문. 두 개의 로프를 사용할 때 하나는 10kg 다른 하나는 20kg 들 수 있다면 둘이 합쳐서 10kg를 들 수 있는 것이기 때문) 그래서 우선 입력받은 최대 중량의 배열 weigh[]을 내림차순으로 정렬했다. Arrays.sort(int[], Collections.reverseOrder()) (로프를 선택해야 한다면 최대 중량이 높은 애들만 뽑는 것이 유리하기 때문) 뽑힌 애들 중에서 가장 값이 작은 애를 골라야하기 때문에 선택하는 수가 k일때 weigh배열의 k번째 값을 선택한다. 이때 k가 늘어날 수록 로프 하나 당 들 수 있는 중량이 커지기 때문에 weigh[k-1]*k를 해준다. 그 중 가장 컸을 때를 출력하면 끝!

Code

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), w = 0;
		
		Integer[] weigh = new Integer[n];
		for(int i = 0; i < n; i++)
			weigh[i] = scan.nextInt();
		Arrays.sort(weigh, Collections.reverseOrder());
		
		for(int k = 1; k <= n; k++)
			 w = Math.max(w, weigh[k-1]*k);
		System.out.println(w);
	}
}