[백준] 2217번 : 로프 – JAVA [자바]

https://www.acmicpc.net/problem/2217

2217번: 로프

 

---

• 문제

 

 

---

• 문제 풀이

 

백준 2217번 로프는 실버 4 난이도의 수학 및 그리디 문제이다. 이 문제에서는 들 수 있는 물체의 중량이 다를 수 있는 로프 N개가 주어진다. 그리고 로프를 병렬로 연결하면 로프에 걸리는 중량을 나눌 수 있다. 이 문제에서 k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다고 주어졌다. 이때 로프 N개가 주어지고 각각 로프마다 들 수 있는 무게가 주어질 때 이 로프들을 이용해서 들 수 있는 최대 무게를 구하면 된다.

 

우선 로프가 하나만 있으면 당연히 로프가 버틸 수 있는 한계가 최대 중량이 된다.

 

하지만 로프가 2개일 때는 로프의 최대중량이 작은 로프의 무게 * 2 가 로프가 두 개일 때 최대 중량이 된다. 문제에서 주어진 예를 보겠다.

 

예시에서는 로프 2개가 주어지고 각각 들 수 있는 무게가 10과 15이다. 만약에 무게가 20인 물체가 있고 이 두 로프를 써서 들 수 있다. 하지만 만약에 물체의 무게가 21이면 각각 로프에 걸리는 중량은 10.5가 된다. 하지만 첫 번째 로프는 10까지밖에 버티지 못하기 때문에 이 물체를 들 수 없다.

 

이걸 N개의 로프의 적용해 보면 이 N개의 로프 중에서 가장 작은 무게 * N이 된다. 하지만 모든 로프를 사용하지 않아도 된다. 따라서, 다음과 같은 공식을 구할 수 있다.

 

최대 무게 = min( 병렬 연결된 로프의 중량 ) * 병렬 연결된 로프의 수

 

다른 예시를 한번 보겠다.

 

4
30
25
20
10

 

먼저 이 무게들을 배열에 저장한 후 내림차순으로 정렬해 준다. 

 

그리고 최대중량이 제일 큰 로프순으로 꺼내면서 순서대로 병렬로 연결한다 는 개념으로 계산하면 된다.

1)  중량 30 로프가 꺼내지고 최대 중량은 30이 된다

2) 중량 25 로프랑 병렬로 연결되면서 최대 중량은 50이 된다.

3) 중량 20 로프가 꺼내지고 먼저 꺼내진 30, 25 로프랑 병렬 연결 되면서 20 * 3 해서 최대 중량은 60

4) 중량 10 로프가 꺼내지고 먼저 꺼내진 30, 25, 20 로프랑 병렬 연결 되면서 10 * 4 해서 최대 중량은 40

이 중에서 제일 최대 중량이 큰 병렬연결은 30, 25, 20 로프의 최대 중량 60 이 된다.

 

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;

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());
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());  //수 입력받기
        }
        Arrays.sort(arr, Collections.reverseOrder());  //내림차순으로 정렬하기
        int total = 0;
        for (int i = 0; i < n; i++) {
            total = Math.max(total, arr[i] * (i+1));
        }
        System.out.print(total);
    }
}