백준 알고리즘 2217

BOJ 2217

분류에 그리디 알고리즘으로 들어가 있어서 풀어봤는데 도저히 그리디 방식으로는 풀 방법을 못찾겠어서 완전탐색으로 풀었습니다.

우선 예제는 10, 15가 주어져서, 마치 무게가 낮은 로프를 선택한 뒤 전체 로프 수를 곱하면 되는 것처럼 느껴졌습니다.

그런데 10,15가 아니라 1,10,15면 1을 선택 할 경우 최대 중량이 3밖에 안되어 여전히 10을 선택할 때 최선의 선택이 되었습니다. 그래서 역순으로 배열을 정렬한 뒤 한개를 선택했을 때 버틸 수 있는 최대 중량, 두개를 선택했을 떄 버틸 수 있는 최대 중량, 이렇게 계속 비교하면서 for문을 종료했습니다.

 

제 코드는 아래와 같습니다.

public class Main {
	private static int N;
	private static Integer res = 0;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Integer arr[] = new Integer[N];

		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(arr, Collections.reverseOrder());

		for(int i = 0; i<N; i++) {
			if(res < arr[i] * (i+1)) {
				res = arr[i] * (i+1);
			}
		}
		System.out.println(res);
	}
}