백준 알고리즘 2217번: 로프

문제 정보

---

 

2217번: 로프

 

핵심

---

어렵지 않은 단순 정렬 문제이다. 문제를 정리하자면

물체의 중량이 x일 때, 선택한 로프의 개수가 n개라면, 각 로프는 x/n의 중량을 부담 가능해야 한다

 

문제의 솔루션은 다음과 같다

들수 있는 최대 중량 = 선택한 로프들 중 최소 중량 * 사용된 로프의 수

 

어차피 로프를 많이 선택해 봤자, 각 로프들은 동일한 무게씩 배분한다

1 500 1000 -> 총 3개의 로프를 선택했다고 가정하자, 어떠한 큰 숫자가 나오더라도 첫번째 로프는 1의 중량밖에 들지 못하기 때문에

최대 3의 중량을 가지는 물체 (3/3 = 1)까지 들 수 있다

 

문제의 풀이를 정리해보면, 먼저 로프의 중량 순으로(오름차순) 정렬을 실시한다

그 이유는 적은 중량의 로프를 선택하는 것은 많은 중량의 로프를 선택하는 것보다 메리트가 없기 때문이다

단순히 생각해 봐도, (1 10 20 40 50) 총 5개의 로프가 있을때 이 중 4개의 로프를 선택하려고 한다면 당연히 1을 제외한 로프가 최대값이 나올 것이다

 

그 다음, 각 로프를 선택하는 경우의 수(n개 선택, n-1개 선택 ... 1개 선택)을 확인하면서

들수 있는 최대 중량 = 최소 중량 로프 * 사용된 로프의 수    식을 사용한 최대 중량을 구해주면 된다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Arrays.sort(weights);

        // 들수 있는 최대 중량은 로프 한개가 들 수 있는 최소 중량 * n(사용된 로프의 수)
        int maxWeight = 0;
        for(int i=0; i<N; i++) {
            maxWeight = Math.max(maxWeight, weights[i] * (N-i));
        }

        System.out.println(maxWeight);
    }
}

 

Source Code on GitHub

---