[Java] 백준 2217 : 로프

문제 링크

1.

30분 소요.

머리속으로 어떻게 풀지 생각하면서 멍때리다가 노트에다가 막 끄적여보았는데 바로 아이디어가 떠올랐다.

써보면서 고민하자.

 

 

2.

문제의 예시의 답은 어떻게 나왔을까?

그리디 알고리즘답게 탐욕스러운 사고 기법을 해보았다.

 

$10$만 선택했을 때는 최대 $10$만큼 들어올릴 것이다.

$15$만 선택했을 때는 최대 $10$만큼 들어올릴 것이다.

$10, 15$를 선택했을 때는 $30$이 아닌 $20$만큼 들어올릴 수 있다.

 

왜? $w/k$만큼 들어올릴 수 있으므로 $30$이 되면 $10$짜리 로프는 못버티기 때문이다.

즉, 들어올릴 수 있는 무게는 제일 작은 중량을 기준으로 선택해야한다.

 

다만 문제에서 모든 로프를 사용할 필요가 없다고 했으므로,

1. 내림차순 정렬

2. 1개, 2개, 3개... 선택할 로프 개수를 늘려가며

   "선택할 로프 중 최소값 $\times$ 개수" 의 최대값을 출력한다.

 

 

3.

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        Integer[] lope = new Integer[n];
        for (int i = 0; i < n; i++) {
            lope[i] = sc.nextInt();
        }

        Arrays.sort(lope, Collections.reverseOrder());

        int answer = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, lope[i] * (i + 1));
        }

        System.out.println(answer);
        sc.close();
    }
}

 

 

4.

오름차순 정렬 방법

 

Arrays.sort(lope, Collections.reverseOrder());