[알고리즘 문제] 백준2217 - 로프

이 문제는 주어진 로프를 사용해서 들어올릴 수 있는 최대 중량의 값을 구하는 문제이다. 입력으로 각 로프가 들어올릴 수 있는 최대 중량이 주어지고, 출력은 이 로프들을 사용하여 들어올릴 수 있는 최대 중량을 출력하면 된다. 

 

이 문제의 조건은 다음과 같다.

 

1. 각 로프가 들어올릴 수 있는 무게는 다르다.

2. k개의 로프를 사용하여 w중량을 들어올린다면, 각각의 로프에는 모두 고르게 w/k만큼의 중량이 걸리게 된다.

3. 로프를 모두 사용하거나, 임의로 몇개의 로프를 골라서 사용해도 된다.

 

 

문제해결 아이디어는 다음과 같다.

 

1. 먼저 입력받은 중량값을 정렬한다. 이는 최대중량을 가진 로프부터 검사하기 위해서 이다.

2. 들어올릴 수 있는 중량이 가장 큰 로프를 list에 넣고, 그 다음 로프와 협력햇을 때 들어올릴 수 있는 중량의 최대값을 list에 넣는다.

3. 로프가 존재할떄까지 2번을 반복하고, 마지막으로 list의 최대값을 출력한다.

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] ropes = new int[n];

        for (int i = 0; i < n; i++) {
            ropes[i] = sc.nextInt();
        }

        Arrays.sort(ropes); // 오름차순으로 정렬

        int max = ropes[ropes.length - 1];
        int rope;
        int count = 1;
        List<Integer> result = new LinkedList<Integer>(); // 중량들을 저장하는 리스트

        result.add(max);

        for (int i = ropes.length - 2; i >= 0; i--) { // 각 로프들과의 협력했을 때 최대 얼마의 중량을 들 수 있는지 검사
            rope = ropes[i];
            count++;
            max = count * ropes[i];
            result.add(max);
        }
        System.out.println(Collections.max(result));
    }
}

처음에 ropes에 각가의 로프가 들어올릴 수 있는 최대 중량을 입력받는다. 그리고 ropes를 오름차순으로 정렬해주는데 이렇게하면 ropes의 맨 뒤에 제일 큰 값이 들어가게 된다. 결국에는 로프를 사용해서 들어올릴 수 있는 최대 중량을 구하는 문제이기 때문에 제일 큰 값부터 시작한다. result는 각각의 로프들이 협력하여 들어올릴 수 있는 최대 중량이 들어가고, 여기서 최대값이 우리가 구하는 답이 된다.

 

max는 ropes의 맨 뒤 값으로, 먼저 result에 넣어준다. 그 다음으로 ropes-2부터 각각의 rope와 협력해서 들어올릴 수 있는 최대 중량을 구하는데, 방법은 다음과 같다.

 예를 들어 [ 5, 10, 15, 20]의 경우[ 15, 20 ]의 경우를 생각하면, 현재 협력하는 로프의 개수는 2개이고, 로프중에서 최소값을 15이다. 최대중량은 로프의 수만큼 똑같이 무게가 가해지므로(최대중량/로프의 수), 이 가해지는 무게가 각 로프의 최대중량을 넘어서는 안된다(모임에서 회비를 정하는데, 나는 100만원을 낼 수 있지만 다른 회원이 5만원 밖에 못내면 나도 같이 5만원을 내야하는 경우)

그러므로 앞의 계산을 다시 보면 최대중량 = 로프중에서 최소값 X 로프의 수가 되며, [ 15, 20 ]에서 최대중량은 30이 된다(최대 중량이 40이면, 40/2 -> 20은 되지만 15가 안된다)