[BOJ] 2217. 로프 (🥈, 그리디)

🔗

풀이

로프들을 사용해서 들어올릴 수 있는 최대 중량을 구하는 문제이다. 모든 로프를 사용하지 않아도 되고 로프를 사용해서 들어올릴 때는 각 로프에 중량(w)을 들어올리는 로프의 개수(k)로 나눈 만큼 무게가 가해지게 된다.

중량이 높아질수록 각 로프에 가해지는 무게도 높아지게 되기 때문에 이 무게들을 버티기 위해서는 버틸 수 있는 중량의 무게가 무거운 로프들 위주로 계산하는 게 유리하다.

여러 개의 로프가 있을 때 들어올릴 수 있는 중량의 무게를 계산하기 위해서는 우선 여러 개 로프 가운데 버틸 수 있는 중량이 최소인 로프를 찾아야 한다. 각 로프에 가해지는 중량이 w/k이기 때문에 중량이 최소인 로프만 버틸 수 있다면 다른 모든 로프들도 버틸 수 있기 때문이다. 최소 로프의 중량을 찾아 로프의 개수(k)만큼 곱하게 되면 전체 로프들이 버틸 수 있는 중량을 구할 수 있다.

결국 내림차순으로 정렬하여 버틸 수 있는 중량의 무게가 높은 로프들부터 낮은 로프들 순서대로 다 합쳐서 들었을 때 최대로 들 수 있는 무게를 구하면 된다. 현재까지 구한 로프의 개수는 i 이고 최소 중량 로프는 내림차순으로 되어있으므로 현재 로프의 중량 rope[i]이 된다.

자바 문법

Arrays.stream(rope).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();

int[] 배열을 내림차순 정렬. Interger[] 로 박싱한 후 내림차순 정렬하고 다시 int[] 배열로 변환하여 반환.

// 로프

import java.io.*;
import java.util.*;

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

        rope = Arrays.stream(rope).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();
        
        int max_weight = 0;
        for (int i = 0; i < rope.length; i++) {
            int tmp = rope[i] * (i+1);
            if (max_weight < tmp) {
                max_weight = tmp;
            }
        }
        System.out.println(max_weight);
    }
}