[백준] 2217 로프 (코틀린 kotlin)

 

문제 링크

 

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

2217번: 로프

 

 

문제 풀이

 

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val weights = Array(n) { 0 }
    for (i in 0..< n) {
        weights[i] = readLine().toInt()
    }
    weights.sort()
    var maxWeight = weights[0] * n
    for (i in 0..< n) {
        maxWeight = max(maxWeight, weights[i] * (n - i))
    }
    println(maxWeight)
}

 

 

처음에 단순히 생각할 때는 sort 해서 제일 작은 것 기준으로

전체 개수를 곱한게 제일 크지 않을까 하는 생각을 했습니다.

하지만 아래 반례와 같은 경우에 바로 틀리게 됩니다.

 

3

10

20

30

입력 예시가 다음과 같이 주어질 때,

10 * 3 보다 20 * 2를 했을 때 더 큰 중량을 만들어낼 수 있습니다.

그리고 이 간단한 예시에서

arr[0] * n, arr[1] * (n - 1), arr[2] * (n - 2) ... , arr[n - 1] * 1 중 max 값이

답이 된다는 것을 알 수 있습니다.

 

위 코드는 오름차순 정렬 후 위에서 구한 공식에 따라 max 값을 구해내는 코드입니다.