[백준] 2217번 로프

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

2217번: 로프

 

만약, 문제에서 '모든 로프를 사용해야한다.' 는 조건이 있었다면, 가장 약한 로프의 중량 * N 을 해서 쉽게 답을 구할 수 있을 것이다.

하지만 모든 로프를 사용하지 않아도 되기에, 모든 경우를 비교하여 문제를 풀었다.

 

1. 배열에 모든 로프(가 버틸 수 있는 중량) 를 담는다.

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

3. 배열의 0 ~ N-1까지 반복하며 가장 큰 최대 중량을 구한다.

 

위와 같은 방식으로 문제를 해결할 수 있다.

 

package yejin.song;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_로프 {

    public static int N;
    public static int arr[];

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

        N = Integer.parseInt(br.readLine());
        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 now = arr[i] * (N-i);
            max = Math.max(max, now);
        }

        System.out.println(max);
    }
}

 

 

++ 해당 문제에 적용 하기엔 복잡하지만, 배열 정렬의 경우 시간복잡도가 O(N log N)이다. 반면 우선순위 큐로 정렬할 경우 시간복잡도가 O(log N) 으로 훨씬 복잡도가 낮다. 나중에 더 복잡한 정렬이면 우선순위큐로 구현해봐야겠다는 생각이 문득 들었다.