[백준 2217] 로프 (Java)

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

2217번: 로프

접근 방법

그리디 알고리즘으로 접근해야하는 문제이다.

 

N개만큼 각 로프가 들 수 있는 중량을 입력 받는데

해당 로프만 사용하는 경우는 그 중량만큼만 들 수 있는데

병렬로 연결하면 무게가 분산되어 그 이상을 들 수 있게 된다.

 

k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 

각각의 로프에는 모두 고르게 w/k만큼의 중량이 걸린다는 말을 주목해보자.

예를 들어, 중량이 20인 무게를 2개의 로프로 든다고 할 때

각 로프에는 20/2 = 10의 중량이 걸린다.

이는 각 로프는 적어도 10의 중량을 들을 수 있어야 한다는 말이다.

 

결국, 병렬로 연결할 때 최대 중량을 결정하는 것은

포함된 로프들 중 가장 적은 중량을 드는 로프가 버틸 수 있는 중량인 것이다.

 

4, 10, 15의 최대 중량을 갖는 로프들이 있을 때

먼저 기준으로 두어야 할 것은 가장 최고 중량인 15이다.

만약 나머지 로프를 더해서 드는 중량이 15 로프 하나만 사용할 때 들 수 있는 중량보다 적다면

15 로프 하나만 사용하는 것이 더 낫다.

 

4 로프가 선택한 로프들 중 가장 적은 중량의 로프라고 할 때

2개 로프일 때 4 * 2 = 8 로 15보다 작으므로 사용 x

3개 로프일 때 4 * 3 = 12 로 15보다 작으므로 사용 x

결국 이 조건에서는 4 로프는 필요가 없는 것이다.

 

10 로프가 선택한 로프들 중 가장 적은 중량의 로프라고 할 때

2개 로프일 때 10 * 2 = 20 으로 15보다 크므로 사용 o

15만 사용할 때보다 10, 15 로프를 같이 사용할 때 더 많은 중량을 들 수 있기 때문에 이 경우가 답이 된다.

 

이를 코드로 구현하기 위해서는 입력 받은 로프의 중량에 대해 정렬을 해야한다.

가장 마지막에 있는 로프가 가장 많은 중량을 들기 때문에 마지막 무게를 시작 max값으로 둔다.

 

그 다음 for문으로 차례로 적은 무게의 로프를 탐색한다.

선택된 로프가 로프들 중 가장 적은 무게라고 생각하고

(해당 로프 중량 * 해당 로프부터 마지막 로프까지의 갯수)를 max와 비교한다.

 

해당 로프가 max를 넘기지 못하면 이 로프는 사용하지 않는 로프로 판정하고,

다음 로프로 넘어간다. 이전 로프는 사용하지 않는 것으로 판정하기 때문에

사용하는 로프의 갯수에서 제외하므로 계산 시 유의한다.

 

소스 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] ropes = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            ropes[i] = scanner.nextInt();
        }

        Arrays.sort(ropes);

        int max = ropes[N];

        for (int i = 1; i < N; i++) {
            max = Math.max(max, ropes[i] * (N - (i - 1)));
        }

        System.out.println(max);
    }
}