BOJ) 로프

로프

2217번: 로프

 

풀이

 

냉정하게 판단하자면 아주 간단한 문제다.

병렬로 로프를 연결하면, 각 로프에 가해지는 무게를 똑같은 무게로 나누어 가질 수 있다는 조건이 있다.

그리고, 각 로프가 최대 견딜 수 있는 하중이 주어진다.

 

1 2 3 4 5 라는 각각 하중을 버틸 수 있는 로프가 주어진다면,

5 하나만 쓰는 것이 가장 무거운 무게를 들 수 있는지, 5 4를 합쳐서 드는 것이 합리적인지 따져가면 되는것이다.

 

그래서 우선 입력받은 로프를 정렬해주었다.

자바의 Arrays.sort에 Collections.reversorder가 적용되는지 몰라서 그냥 Array.sort로 오름차순으로 정렬하고 배열의 맨 끝부터 탐색했다.

가장 무거운 무게 하나로 하나의 물건만 드는 것이 가장 큰 값인지,

그 다음 버틸 수 있는 무거운 무게로 두개의 로프를 드는 것이 가장 좋은지 판별했다.

위의 과정이 int k = n-i (로프의 갯수), int w = ropes[i] (버틸 수 있는 무게의 최대 값),  Math.max(answer, w*k) 코드의 전부다.

 

알고리즘을 물어보기보다는 수학적인 사고를 요한 문제같다.

 

코드

 

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

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[] ropes = new int[n];

        for(int i=0; i<n; i++) {
            ropes[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        solution(n,ropes);
    }

    private static void solution(int n, int[] ropes) {
        int answer = 0;
        Arrays.sort(ropes);

        for(int i=n-1; i>=0; i--) {
            int k = n-i;
            int w = ropes[i];
            answer = Math.max(answer, w*k);
        }
        System.out.println(answer);
    }
}