22.03.15 - [BOJ] 2217. 로프

[suhyunsim]

문제

• 로프

핵심 아이디어

• 일단 사용할 로프의 개수를 결정했다고 생각 -> 어떤 로프를 선택할까?
  • -> 당연히 가장 최대 중량이 큰 로프 k개를 선택
  • 귀류법으로 증명: 최대 중량 순으로 선택하지 않았을 때 최대 중량이 가장 낮은 로프의 중량은 가장 최대 중량이 큰 로프들을 선택했을 때보다 클 수 없음
  • 로프의 최대 중량을 결정, 로프를 k개 고른다면 => w[n - k] * k

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q2217;

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] weight = new int[n];
        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
        }
        Arrays.sort(weight);
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            answer = Math.max(answer, weight[n - i] * i);
        }
        System.out.println(answer);
    }
}