[백준][KOTLIN] 2565 전깃줄

- https://www.acmicpc.net/problem/2565

2565번: 전깃줄

풀이

1. 전봇대 번호를 저장할 2차원 배열을 선언한다.(0 : A 전봇대, 1 : B 전봇대)

2. 겹치는 조건을 찾는 것은 복잡하므로 역으로 교차하지 않는 최대 전깃줄 수를 구해서 전깃줄 전체 개수에서 뺀다.

3. 교차하지 않는 최대 전깃줄을 구하기 위해서 A를 기준으로 잡고 오름 차순으로 정렬 한다.(Array.sort comparable lamba 사용)

4. 3번에서 정렬된 배열의 B 값의 가장 긴 부분 수열(LIS)의 개수를 구한다.

5. 전체 전기줄 개수에서 4번의 결과를 뺀다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    // 0: A 전봇대 값, 1: B 전봇대 값
    val wire = Array(N + 1) {
        IntArray(2)
    }

    for (i in 1..N) {
        val st = StringTokenizer(br.readLine())
        wire[i][0] = st.nextToken().toInt()
        wire[i][1] = st.nextToken().toInt()
    }

	// A 전봇대를 기준으로 오름 차순 정렬
    Arrays.sort(wire) { a, b ->
        when {
            a[0] - b[0] > 0 -> 1
            a[0] < b[0] -> -1
            else -> 0
        }
    }

    // 정렬된 배열의 B값에 대한 가장 긴 부분 수열의 수(LIS) 구한다.
    val dp = IntArray(N + 1)
    var result = Int.MIN_VALUE

    for (i in 1..N) {
        var count = 0
        for (j in 1 until i) {
            if (wire[i][1] > wire[j][1]) {
                count = max(count, dp[j])
            }
        }

        dp[i] = count + 1
        result = max(result, dp[i])
    }

    // 겹치지 않는 전기줄의 수를 구했으므로 출력은 전체 개수에서 전기줄의 수를 뺀다.
    println("${N - result}")
}

private fun max(a: Int, b: Int): Int {
    return if (a < b) b else a
}