자바 그리디 - 백준 2217 로프

문제

---

 

 

 

 

문제해결

---

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

public class B2217 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();//총 로프 개수
		int[] ropes = new int[size];//각 로프가 버틸수 있는 중량
		for(int i=0;i<size;i++)
			ropes[i] = sc.nextInt();
		//로프 정렬
		Arrays.sort(ropes);
		//로프들로 가장 많이 들수 있는 중량
		int result = ropes[0]*size;
		for(int i=0;i<size;i++) {
			int tmp = ropes[i]*(size-i);
			if(tmp>result)
				result = tmp;
		}
		System.out.println(result);
	}
}

- 모든 로프를 사용해야 한다면 들수 있는 최대 무게는 "제일 적게 드는 로프 X 로프 개수" 일 것이나 모든 로프를 사용할 필요는 없다는 조건이 있으므로 모든 조건을 살펴봐야된다

- 만약 총 로프 개수가 3이고, 각각 10, 80, 90의 무게를 들 수 있으면, 3개의 로프 사용시 총 30의 무게를, 2개의 로프 사용시 총 160의 무게를, 1개의 로프 사용시 90의 무게를 들 수 있다.

- 그러므로 우선 로프들을 오름차순 정렬 후 몇개의 로프를 사용 시 가장 많은 무게를 들수 있는지 구하면 된다.