백준 2217번 로프

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

테스트 케이스

입출력 1

입력

2
10
15

출력

20

입출력 2

배열 sort 의 중요성을 보여주는 예제. Sort 없이 처음부터 loop 을 돌게되면 9 가 아닌 5가 나올 수 있다.

입력

5
1
2
3
4
5

출력

9

입출력 3

배열 sort 하고 나서도 배열 전체를 훓어야 되는 이유를 보여주는 예제. max 에서부터 시작하는 경우, 11 다음 7에서 loop 을 빠져나오면 \((11*2 = 22 > 21 = 7*3)\) 6*4=24 가 아닌 22가 나올 수 있다.

입력

4
6
7
11
15

출력

24

입출력 4

배열 sort 하고 나서도 배열 전체를 훓어야 되는 이유를 보여주는 예제(2). min 에서 시작하는 경우, 13 다음 15에서 loop 을 빠져나오면, \((13*5=65 > 60= 15*4)\), 23*3 = 69 가 아닌 65가 나올 수 있다.

입력

6
1
13
15
23
24
25

출력

69

Answer(1)

max 를 이용한 답

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[] ropeWeights = new int[n];
        int max = 0;

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

        Arrays.sort(ropeWeights);

        for (int i = n-1; i >= 0; i--) {
            int numRope = n - i;
            int tempWeight = ropeWeights[i] * numRope;
            max = (tempWeight > max) ? tempWeight : max;
        }
        System.out.println(max);
    }
}

Answer(2)

min을 이용한 답

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[] ropeWeights = new int[n];
        int max = 0;

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

        Arrays.sort(ropeWeights);

        for (int i = 0; i < n; i++) {
            // we know ropeWeights[i] is the minimum
            int numRope = n - i;
            int tempWeight = ropeWeights[i] * numRope;
            max = (max < tempWeight) ? tempWeight : max;
        }
        System.out.println( max);
    }
}

Notes

• goal: max(weight using 1 or more ropes given)
• \[\frac{w}{n} = min(\text{선택된 rope 무게들})\]
• we want \(max(w)\) where \(w = n * min(\text{선택된 rope 무게들})\), and \(n = \text{사용된 rope 갯수}\)
• 주어진 rope 모두 사용 안해도 됌. (\(n \geq 1\))
  • n= 1 이라면, 주어진 rope 무게 중 max 가 답이다.
  • n= 2 이라면, max(2번째로 큰 max 인 로프 무게 *2 , max로프 무게) 가 답이다.

Reference

The problem is taken from baekjoon