[백준 2217번] 로프 - Greedy Algorithm

백준 2217번 그리디 알고리즘(Greedy Algorithm)을 통해 풀이하는 문제이다.

정답률이 높았던만큼 큰 고민없이 쉽게 풀 수 있던 문제였다.

 

문제는

N(1 ~ 100,000)개의 로프가 있다. 여기서 로프를 이용해서 중량이 w인 물건을 들어올릴 수 있는데 로프를 병렬로 연결해서 물체를 들어올리면 (w/로프의 개수)의 중량으로 들 수 있다. 여기서 로프를 사용해서 들 수 있는 최대 중량을 구하는 것이 문제였다.

 

문제의 답을 찾는 과정을 생각하는 것이 크게 어렵지 않았다.

각 로프가 버틸 수 있는 중량이 주어지는데 주어진 중량 중에 가장 버틸 수 있는 중량이 적은 로프가 버틸 수 있는 무게가 로프 몇개일 때, 가장 큰지 찾으면 됐다.

 

우선 각 로프가 버틸 수 있는 크기를 오름차순으로 정렬하고 찾아나갔다.

그렇다면 높은 중량을 버티는 줄일 때는, 그 밑의 중량을 버티는 로프를 빼고 총량을 계산하면 됐다.

이를 식으로 세우면 다음과 같다.

// weights는 각 로프가 버틸 수 있는 중량을 오름차순으로 정렬한 배열이다.
// 즉, i번째 로프는 그보다 가벼운 로프들은 버틸 수 없기 때문에 총량에서 제외하고 계산한다.
for (int i = 0; i < N; i++) {
    int totalWeight = weights[i] * (N-i);
    if (totalWeight > max) { max = totalWeight; }
}

 

이 과정을 통해 가장 큰 값을 찾아나서면 된다.

 

전체 소스코드는,

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

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

        int N = Integer.parseInt(br.readLine());
        int[] weights = new int[N];

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

        Arrays.sort(weights);
        int max = 0;

        for (int i = 0; i < N; i++) {
            int totalWeight = weights[i] * (N-i);
            if (totalWeight > max) { max = totalWeight; }
        }

        System.out.println(max);
    }
}