[백준] 2217번: 로프

문제링크 : https://www.acmicpc.net/problem/2217

 

문제풀이

각 로프의 최대 중량이 아래와 같다고 하면,

1) 5짜리 로프를 선택, 최대 5만큼의 중량이 걸린다고 하면,

   세 로프로 들 수 있는 최대 중량은 5 X 3 = 15가 된다.

 

2) 8짜리 로프를 선택, 최대 8만큼의 중량이 걸린다고 하면, 5짜리 로프로는 들 수 없다. (최대가 5이므로)

   따라서 8, 13짜리 로프에 각각 8씩 걸리게 되어 최대 중량은 8 X 2 = 16이 된다.

 

3) 13짜리 로프를 선택, 최대 13만큼의 중량이 걸린다고 하면, 5와 8짜리 로프는 사용할 수 없다.

   따라서 13짜리 로프로 들 수 있는 최대 중량은 13 X 1 = 13이 된다.

 

따라서 이 경우 최대 중량은 2번으로 도출된 16이 된다.

 

 

이 문제는 그리디 알고리즘이 적용된다.

그리디 알고리즘이란 매 순간 최대가 되는 경우를 선택하는 알고리즘인데,

위에서도 보이듯이 각 로프를 선택했을 때 최대로 걸리는 중량으로 총 중량을 계산하고 있다.

 

 

소스코드

package baekjoon;

import java.io.*;
import java.util.Arrays;

public class P2217 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] weight = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(weight);
		
		int maxWeight = 0;
		for (int i = 0; i < N; i++) {
			int sum = weight[i] * (N - i);
			if (maxWeight < sum) maxWeight = sum;
		}
		
		System.out.println(maxWeight);
		
		br.close();
	}
}