[백준] 2217번 로프 - 자바

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

2217번: 로프

문제 풀이

독해력이 딸리는지 문제 이해하는데 시간이 좀 걸렸다.
간단하게 생각해서 각 로프마다 버틸 수 있는 중량이 입력되고 이 로프를 선택해서 버틸 수 있는 최대 중량을 구해야 한다. 이때 각 로프는 중량(w)/선택된 로프 개수(k)로 일정하게 중량이 분담된다.

그럼 문제를 해결해보자.

우선 어떤 로프를 선택하느냐에 따라 최대 중량이 결정된다.
그럼 선택되는 로프의 기준이 무엇이 되냐면 선택된 로프 중 가장 적은 중량을 버티는 로프이다. 이유는 간단하다.

만약 로프를 k개 선택하면 중량 w에 대해 고르게 w/k만큼 중량이 걸린다는 것에 포인트를 두고, 예시를 들어보겠다.

로프 3개 (5,10,30)를 선택했을 때 버틸 수 있는 최대 중량은 똑같이 5, 10, 30 로프에게 분담된다. 그렇다면 5가 중량을 버틸 수 있어야 하므로 15의 중량이 주어지면 각 로프에 대해 5->5, 10->5, 30->5 의 중량이 분담되므로 3개를 선택했을 때 최고 중량은 15이다

 

그럼 이제 여기서 더 생각해야 해봐야 되는 것은 굳이 3개를 택해야 되나?
그것은 아니다 여기서 30로프 하나만 선택하면 30의 중량을 버틸 수 있어 최대가 된다.

따라서 로프가 주어졌을 때 (선택된 로프 중 가장 최소 중량값) * (선택된 로프의 개수)를 구하기만 하면 된다.

이는 반복문으로 쉽게 구할 수 있으므로 바로 코드를 살펴보자.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringBuilder sb = new StringBuilder();

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

        Arrays.sort(lopes, Collections.reverseOrder());
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, lopes[i] * (i + 1));
        }
        System.out.println(max);
    }
}

오름차순으로 정렬시 로프의 범위를 정해주기 까다롭다
위 예시처럼 로프(5,10,30)이 있을 때 필요한 로프의 범위는 (30), (30,10), (30,10,5)이므로 내림차순으로 해야 깔끔하게 처리 가능하다.
각 범위마다 최대값을 구하여 출력해주면 성공