[백준] 2217 로프

 

🔒 문제

 

 

💡 아이디어

로프를 최대 중량 순으로 선택해야 감당 가능한 최대 무게를 구할 수 있다.

총 로프 선택 개수를 1 부터 N개 모두 해보고 최대 중량을 계산해야한다.

그럼에도 로프 중량을 큰 것 순으로 내림차순 하는게 좋은데

하나의 루프를 돌면서 index + 1 번째 로프가 현재 index + 1 개를 선택한 로프중 가장 작은 로프가 되기 때문이다.

 

로프를 k개 선택했을 때 들 수 있는

$$ 최대 중량값 = 가장\, 작은\, 로프\, 중량\: *\: k개 $$

 

여기서 가장 작은 로프 중량 을 루프 안에서 매번 바로 선택할 수 있다.

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val N = bufferedReader.readLine().toInt()
    var answer = 0

    val ropes = IntArray(N){0}
    repeat(N){idx->
        ropes[idx] = bufferedReader.readLine().toInt()
    }

    // 감당할 수 있는 최대 중량: 최소값 * 로그 갯수
    // 감당할 수 있는 최대 중량을 최대 로프 중량순으로 1개 2개 ... N개 고르는 것으로 모두 해봐야함.
    // 매 라운드마다 최소값을 구하는게 아니라
    // 미리 큰 중량순으로 정렬해두면 됨.
    ropes.sortDescending()
    ropes.forEachIndexed { index, minRopeWeight ->
        // 선택한 로프 개수 == index + 1
        // index + 1번 째 로프는 현재 Loop 에서 가장 작은 중량의 로프.
        val maxWeight = minRopeWeight * (index + 1)
        answer = max(answer, maxWeight)
    }

    println(answer)

}