[백준 2217번] [Kotlin] 로프

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

2217번: 로프

 

난이도 : 실버 4
태그 : 수학, 그리디, 정렬

 

 

설명

n개의 로프가 주어지고, k개의 로프로 w만큼의 물체를 들어올릴때, 각 로프에는 w/k의 부하가 걸립니다.

10를 버틸 수 있는 로프 하나, 15를 버틸 수 있는 로프 하나가 있으면

15개 하나를 사용하는 것 보다는, 10만큼씩 2개를 사용해 20의 무게를 들어올리는게 더 효율적입니다.

 

각각 5, 10, 15, 20, 25를 들어올릴 수 있는 로프가 한 개씩 있다고 가정하면,

5 * 5 = 25

10 * 4 = 20

15 * 3 = 45

20 * 2 = 40

25 * 1 = 25

15만큼 중량으로 3개를 사용하는게 가장 효율적입니다.

구하는 방법은 숫자를  정렬하고,

현재 무게 * (로프 개수 - 지금 로프의 idx)를 하면 됩니다.

 

 

 

소스코드

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {

    val n = readLine().toInt()
    val arr = Array(n) { 0 }
    for (i in 0 until n) {
        arr[i] = readLine().toInt()
    }

    arr.sort()
    var max = arr[0] * n

    for (i in 0 until n) {
        max = max(max, arr[i] * (n - i))
    }

    println(max)
}

 

 

후기

정렬 + 그리디 알고리즘으로 풀 수 있었던 문제였습니다.