백준) 2217 : 로프

⏰문제

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

2217번: 로프

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

192 MB

62492

27562

22050

43.097%

 

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1

2
10
15

예제 출력 1

20

 

💡풀이

그리디를 활용하여 문제를 풀었다. 문제를 보면 로프를 이용해서 들어올릴 수 있는 물체의 최대 중량을 구하라고 하였다. 그리디 알고리즘 관점에서 보면 최대 중량을 들어올릴 수 있는 로프를 사용하는 것이 가장 좋은 것이므로 로프의 중량을 이용해서 정렬을 하였다. 그리고 로프가 버틸 수 있는 최대 중량과 여러 로프를 이용해서 물체를 들어올릴 때 w/k로 로프에 무게가 걸린다고 한다. 이 조건을 보고 로프의 정렬은 걸려있고 for문을 돌면서 마지막에 나온 로프의 최대 중량을 기준으로 사용하려고 하는 로프의 개수를 구하면 된다고 생각했다. 

 

⌨️ 코드

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[] rope = new int[N];
        for(int i=0; i< N; i++){
            rope[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(rope); //오름차순 정렬

        int cnt =0;
        int max =Integer.MIN_VALUE;
        int sum =0;
        for(int i=N-1; i>=0; i--){
            cnt++;
            sum = rope[i]*cnt;

            if(max < sum){
                max = sum;
            }

        }

        System.out.println(max);
    }//main
}