[알고리즘] - 로프 (백준 2217번 문제)

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

문제 해결아이디어

• 모든 로프를 사용해야 할 필요는 없으니 가장 큰 문게를 들 수 있을 때를 추출하면된다.
• 가장 큰 무게를 들수 있는 로프부터 순서대로 병렬로 연결한다는 생각으로 계산한다.

정당성 분석

• 가장 큰 무게를 드는 로프부터 병렬로 연결하는 이유는? 예를 들어 아래 처럼 입력한다고 가정해보자

  5
  35
  33
  30
  20
  12

  {12,20,30,33,35} 순으로 계산해보면

  1. 중량 12 로프가 꺼내지고 최대 중량은 12

  2. 중량 20 로프랑 병렬 연결시 최대 중량은 24

  3. 중량 30 로프랑 병렬 연결시 최대 중량은 36

     이처럼 더 높은 중량 로프가 와도 최대중량은 가장 낮은 무게 * n 이기 때문에 어떤 무게가 와도 의미가 없다.

  • 역순으로 해보자.

  1. 중량 35 로프가 꺼내지고 최대 중량은 35

  2. 중량 33 로프랑 병렬로 연결 되면서 최대 중량은 66

  3. 중량 30 로프가 꺼내지고 먼저 꺼내진 35, 33 로프랑 병렬 연결 되면서 30 * 3 해서 최대 중량은 90

  4. 중량 20 로프가 꺼내지고 먼저 꺼내진 35, 33, 30 로프랑 병렬 연결 되면서 20 * 4 해서 최대 중량은 80

  5. 중량 12 로프가 꺼내지고 먼저 꺼내진 35, 33, 30, 20 로프랑 병렬 연결 되면서 12 * 5 해서 최대 중량은 60

     이처럼 역순으로 해야 다음 중량 로프가 달렸을 때의 최대 중량이 달라진다.

     이중에서 제일 최대 중랼이 큰 병렬 연결은 35,33,30 로프의 최대 중량 90 이다.

시간 복잡도 분석

• 로프의 수를 (N) 이라고 가정한다면 O(N)의 시간복잡도를 가지지만 Arrays.sort()의 함수가 O(NlogN)이기 에 시간 복잡도는 O(NlogN)이다.

해결한 코드

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

public class BJ_2217 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int w = sc.nextInt();
        int[] k = new int[w];

        for (int i = 0; i < w ; i++) {
            k[i] = sc.nextInt();
        }

        Arrays.sort(k);

        long max = 0 ;

        for (int i = w-1; i >= 0; i--) {
            k[i] = k[i] * (w-i);
            if(max < k[i]) max = k[i];
        }

        System.out.println(max);
    }

}