코틀린 백준 2217번 로프

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

2217번: 로프

로프 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

192 MB

38895

16727

13486

42.374%

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

20

 

---

이 문제는 

그리디 알고리즘을 이용하는 문제입니다

이 문제를 어떤 방식으로 풀까 고민했는대

크기가 큰 순으로 정렬 후 

크기가 큰 순으로 하나씩 더해보면서 가장 큰 값을 찾았습니다! 

이때 중요한 점은 각 로프는 w/k 만큼의 중량이 걸린다는 점입니다

 

3개의 로프 a,b,c 가 크기 순 으로 나열되어있다고 가정했을때 

3개의 로프를 이용했을 경우 중량은 가장 작은 c*3이 됩니다 

이런식으로 접근해서 문제를 푼다면 쉽게 풀 수 있었던 문제였습니다!

 

val bre = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()) {

    var count = bre.readLine().toInt()


    var list = ArrayList<Int>()
    var sum = 0
    var max = 0
    for(i in 0 until count){
        var num = bre.readLine().toInt()
        sum += num
        list.add(num)
    }

    list.sortDescending()
    max  = list[0]
    sum = list[0]
    for(i in 1 until list.size){

        var temp   = sum+list[i]

        if(temp.toDouble()/(i+1) >list[i].toDouble()){
            temp = list[i]*(i+1)
        }

        if(temp>max){
            max = temp
            sum = temp
        }

    }
    println(max)
}