백준 2217) 로프

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

2217번: 로프

 

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력

2
10
15

예제 출력

20

 

---

 

이 문제를 그리디 알고리즘으로 풀어야 하는 이유는 다음과 같다.

 

 

주어진 로프들의 최대 무게 중에서 가장 많이 버틸 수 있는 로프 a가 있을 때, (a,b,c .... ) if(a > b)

 

a 하나로 버티는 것과 (a+b(a 다음으로 무게를 버티는 로프)) 로 버티는 것 중에 더 무게를 버티는 것이 무엇인지 판별해야 하기 때문이다.

 

즉, 가장 최댓값부터 욕심내서 최대 중량 제한을 구한다.

 

 

 

문제에 나온 예시를 살펴보겠다.

 

로프가 1개일 경우

 

w / 1 = 10 -> w = 10kg 버틸 수 있음

w / 1 = 15 -> w = 15kg 버틸 수 있음

 

그러므로 15가 maxValue이다.

 

 

로프가 2개일 경우

 

w / 2 = 10 -> w = 20kg

즉, 10kg를 들 수 있는 로프를 포함하면 20kg까지 버틸 수 있다는 의미이므로,

maxValue는 20kg가 된다.

 

 

 

 

반례를 살펴보도록 하겠다. 15, 5 라면 어떻게 되겠는가?

 

로프가 1개일 경우에는 maxValue = 15가 된다.

로프가 2개일 경우에는 5를 추가하는데,

w / 2 = 5 -> w = 10kg 이므로 기존 maxValue보다 작게 된다. 그러므로 5는 포함하지 않는다.

 

 

 

나머지 추가 설명은 아래 코드에 주석으로 첨부하겠다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = IntArray(n) {readLine().toInt()}

    // 배열을 내림차순으로 정렬
    arr.sortDescending()
    // 비교하기 위해 maxValue를 미리 저장
    var maxValue = arr[0]

    for(i in 1 until n) {
        // 다음 로프 x (1+i) 인데 1은 arr[0]의 로프이므로, 로프가 추가될수록 i씩 더함
        if(maxValue < arr[i] * (1+i))
            maxValue = arr[i] * (1+i)
    }
    println(maxValue)
}