[백준] 2798번 : 블랙잭 (Kotlin) + 브루트포스 알고리즘

2798번: 블랙잭

백준 2798번 블랙잭 예제를 통해 브루트포스(Brute Force) 알고리즘에 대해 알아보겠습니다.

브루트포스(Brute Force)

브루트포스는 모든 경우의 수를 탐색하면서 조건에 만족하는 결과를 추출하는 완전탐색 알고리즘입니다.

브루트포스 알고리즘은 모든 경우의 수를 탐색하기 때문에 비용이 많이 들고 시간이 오래 걸린다는 치명적인 단점이 있지만 반드시 조건에 만족하는 결과를 도출해 낸다는 특징이 있습니다.

 

선형적인 구조에서는 비교적 효율적인 탐색이 가능한데 블랙잭 문제를 통해 브루트포스 알고리즘을 적용해 보겠습니다.

---

나의 풀이

fun main(args: Array<String>) {
    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
    val numbers = readLine()!!.split(" ").map { it.toInt() }.toTypedArray().sortedArray()

    var result = 0
    for (i in 0 until N - 2) {
        // 연속한 세 수의 합이 M보다 큰 경우 종료
        if (numbers[i] + numbers[i + 1] + numbers[i + 2] > M) {
            break
        }
        for (j in i + 1 until N - 1) {
            for (k in j + 1 until N) {
                // 세 장의 합
                val sum = numbers[i] + numbers[j] + numbers[k]

                // 세 수의 합이 M보다 작고, 이전에 계산했던 result보다는 클 경우
                if (sum <= M && sum > result) {
                    result = sum
                }
                // 세 수의 합이 M일 경우
                if (sum == M) {
                    println(result)
                    return
                }
            }
        }
    }
    // 세 수의 합이 M과 같지 않지만 가장 근접했던 result 출력
    println(result)
}

☞ 먼저 입력된 수의 배열을 sortedArray()를 통해 선형 구조(오름차순)로 구조화시켜 주었습니다.

비선형 구조라면 입력된 숫자에 대해 모든 세 수의 합에 대한 조합을 탐색해야 합니다. 하지만 이제 선형 구조를 탐색하기 때문에 특정 조건에서 더 이상 탐색할 필요가 없다고 판단되면 프로그램을 종료시켜 탐색시간을 줄일 수 있습니다.

따라서 저는 연속한 세 수의 합이 M보다 크면 이후에 탐색할 세 수의 합은 항상 M보다 클 것이기 때문에 직전의 result를 출력하고 프로그램을 종료하도록 작성했습니다.