[백준 JAVA] 2217 로프

2217 로프

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

문제설명

그리디 알고리즘을 사용하여 주어진 로프들로 최대 하중을 지탱할 수 있는 방법을 찾기

 

• 주어진 N개의 로프가 있으며, 각 로프는 특정 하중까지 지탱할 수 있다.
• 로프를 여러 개 묶어서 사용할 때, 전체 하중은 묶인 로프의 최소 하중에 따라 결정된다.
• 로프들을 최적의 조합으로 사용하여 가능한 최대 하중을 계산다.

 

접근방식

O(N log N)  시간복잡도

 

N개의 로프 정보를 받고 

배열을 오름차순으로 정렬한다.

 

문제 조건 분석 과정

 

• 입력받은 로프의 하중을 내림차순으로 정렬한다. (가장 강한 로프를 먼저 고려)
• 정렬된 배열의 각 로프의 하중을 (N - i)로 곱한다.
• 여기서 N - i는 현재 로프와 그 이후의 로프를 묶었을 때 사용할 수 있는 로프의 개수이다.
• 이 값들 중 최대값을 찾아 출력한다. 최대값이란, 로프들을 묶었을 때 가능한 최대 하중이다.

 

사용된 자료구조

• 배열: 로프의 최대 하중을 arr에 담는다. 배열의 인덱스는 로프의 순서를 나타내며,
• 각 값은 해당 로프의 최대 하중을 나타낸다.
• 정렬: 배열을 정렬하여 가장 큰 하중부터 순서대로 계산한다.

전체코드

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[] arr = new int[N];
        int max = 0;

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

        Arrays.sort(arr);

        //배열의 요소에 N - i를 곱한 후 최대값 갱신
        for(int i = 0; i < N; i++){
            arr[i] *= (N - i); //현재 요소에 (N - i) 곱함
            if(max < arr[i]) max = arr[i]; //최대값 갱신
        }

        System.out.println(max);
        br.close();
    }
}