[Java] 백준 2217 로프 - 실버4

 

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

2217번: 로프

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();

        for (int i=0; i<cnt; i++) 
            list.add(Integer.parseInt(br.readLine()));

        Collections.sort(list);

        int maxWeight = list.get(0) * cnt;
        for (int i =1; i<cnt; i++) {
            Integer min = list.get(i);
            if (min * (cnt-i) > maxWeight) 
                maxWeight = min * (cnt -i);
        }

        //w <= min * k
        System.out.println(maxWeight);
    }
}

• k개의 로프가 들 수 있는 최대 중량은 (로프 리스트 중 들 수 있는 중량이 최소인 애) * k이다.
  • w/k  <=  min 이기 때문
  • 가장 작은 로프가 중량을 견디지 못하면 물체를 들 수 없기 때문에 최솟값에 맞춰진다
• list를 오름차순으로 정렬한 후
• 최솟값을 하나씩 빼면서 모든 가능한 중량을 테스트하고, 최대 중량을 maxWeight에 저장한다
  • 이 때 중량은 min값 * (list.size() - min값의 인덱스) 로 구한다

 

 

 

인터넷에 다른 풀이들을 찾아봤지만, 내 풀이와 거의 동일했다.