[Baekjoon] 2217 - 로프

📝 문제

 

 

🔑 풀이 과정

· k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

→ 이는 모든 로프가 동일한 중량을 들어야 한다는 것을 의미한다.

 

· n개의 로프를 사용해서 들어 올릴 수 있는 최대 중량은 n개 로프 중 가장 적게 버틸 수 있는 로프의 최대 중량 * n

 

· 문제의 설명에서 "모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다." 라는 조건이 나와있다. 우리는 n개의 로프가 있을 때, n개 로프를 다 사용했을 때 최대 중량, n-1개 로프를 사용할 때 최대 중량, n-2개 로프를 사용할 때 최대 중량 ... 1개의 로프를 사용했을 때 최대중량을 구해서 그 중 가장 큰 값을 구하면 된다.

 

· 위에 적어둔 사용할 수 있는 로프중 제일 적은 중량 * 사용 가능한 개수 공식을 사용하면 된다. 제일 적은 중량을 사용하기 위해 배열을 정렬해준다.

 

· 풀이 과정

 

 

🔓 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        //정렬
        Arrays.sort(arr);

        //계산
        int max = 0;
        for(int i = 0; i < N; i++){
            int sum = arr[i] * (N-i);

            if(sum > max)
                max = sum;
        }

        //출력
        bw.write(max + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 그리디 알고리즘

- 정렬