[백준, Brute-Force, Kotlin] P.2798 블랙잭

 

1. 딜러가 부른 값에 일치하거나 가장 근접한 값을 꺼내야 하므로, Priority Queue를 활용하기로 결정하였습니다.
(내림 차순 정렬)

2. 전체 탐색을 하여 계산한 결과가 딜러가 부른 값을 초과하지 않을 경우 pq에 저장합니다.

3. 전체 탐색 과정 중 딜러가 부른 값과 같은 결과가 나오면 전체 탐색을 중단하고 결과를 리턴합니다.(나름의 성능 개선?)

4. pq에 값을 한개 꺼내 출력합니다.

 

import java.util.*

var N:Int = 0
var M:Int = 0

fun main(args: Array<String>) {
    val scr = Scanner(System.`in`)

    N = scr.nextInt()
    M = scr.nextInt()

    var arr = IntArray(N) { -1 }

    for(i in 0 until N) {
        val element = scr.nextInt()
        arr[i] = element
    }

    val pq = calculate(arr)

    println(pq.poll())
}

fun calculate(arr: IntArray): PriorityQueue<Int> {
    val pq = PriorityQueue<Int>(kotlin.Comparator { o1, o2 ->
        o2 - o1
    })

    for(i in 0 until N) {
        for(j in i+1 until N) {
            for(k in j+1 until N) {
                val num = arr[i] + arr[j] + arr[k]

                if(num == M) {
//                    println("Hit")
                    pq.add(num)
                    return pq
                }

                if(num > M) {
                    continue
                }

                if(num < M) {
                    pq.add(num)
                }
            }
        }
    }

    return pq
}