[백준] 2217 로프 - JAVA

문제

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

 

예제 입력

2
10
15

 

예제 출력

20

 

내 코드(448ms)

- (선택한 밧줄 중에 가장 작은 숫자 * 밧줄 수) 가 최대 중량이 됨으로 밧줄 무게들을 내림차순으로 해서 첫번째 수부터 하나씩 더해 밧줄수를 1개씩 증가시키고, 끝에 있는 숫자로 중량을 계산해본다.

- Math.max로 계산한 중량값들을 저장해 새로 계산한 값과 비교해서 더 큰수를 중량값으로 넣어준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int total = Integer.parseInt(br.readLine());
		Integer[] weight = new Integer[total];
		
		for(int i=0; i<total; i++) {
			weight[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(weight, Collections.reverseOrder());
		
		int result = 0;
		for(int i=1; i<=total; i++) {
			result = Math.max(result, weight[i-1]*i);
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(String.valueOf(result));
		br.close();
		bw.close();
	}
}

 

다른 사람 코드(280ms)

- 무게를 Index값으로 받아서 배열 값은 밧줄의 갯수를 넣어줬다.

- 최소 index에 밧줄의 개수를 곱해서 최대 중량값과 비교를 통해 최대 중량값을 갱신한다.

import java.io.*;

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

        int n = Integer.parseInt(br.readLine());

        int rope[] = new int[10001];
        int min = 10001;
        int max = -1;

        for(int i = 0; i < n; i++){
            int weight = Integer.parseInt(br.readLine());
            if(weight < min) min = weight; //min은 가장 적은 중량을 받칠수 있는 로프
            if(weight > max) max = weight; //max은 가장 많은 중량을 받칠수 있는 로프
            rope[weight]++;
        }

        int prevWeight = min;
        int line = n;
        int maxWeight = prevWeight * n;//maxWeight는 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량
        line -= rope[prevWeight];

        for(int i = prevWeight + 1; i <= max; i++){
            if(rope[i] > 0){
                if(maxWeight < i * line)
                    maxWeight = i * line;
                line -= rope[i];
            }
        }

        bw.write(String.valueOf(maxWeight + "\n"));
        bw.flush();

        br.close();
        bw.close();
    }
}