[Algorithm] 백준 - 블랙잭 (2798) (Kotlin)

 

이 문제도 브루트 포스 알고리즘을 써서 풀 수 있다. 카드 3장의 합이 M 이하면서 M에 가장 가까운 값을 찾아야 한다.

반복문 3개를 사용해서 카드를 3개씩 선택하는 경우를 구현할 수 있다.

 

fun main() {
    val (N, M) = readln().split(" ").map { it.toInt() }
    val cards = readln().split(" ").map { it.toInt() }
    var maxSum = 0

    for (i in 0 until N) {
        for (j in i + 1 until N) {
            for (k in j + 1 until N) {
                val sum = cards[i] + cards[j] + cards[k]
                if (sum <= M) {
                    maxSum = maxOf(maxSum, sum)
                }
            }
        }
    }
    println(maxSum)
}

 

입력받는 부분을 적당히 만들고 최대값을 담을 변수를 선언해둔다. 그리고 3중 반복문으로 카드 3장을 선택하는 상황을 구현한다.

어떻게 이 코드가 카드 3장을 고르는 상황을 구현하는가? 이 반복문은 아래처럼 작동한다.

 

• 1번 반복문(i) : 1번 카드 선택
• 2번 반복문(j) : j는 i+1부터 시작해서 중복 선택을 피해 2번 카드 선택
• 3번 반복문(k) : k는 j+1부터 시작해서 중복 선택을 피해 3번 카드 선택

 

이렇게 되기 때문에 문제의 테스트 케이스가 주어진다면 5, 6, 7의 카드가 선택된다.

그리고 다중 반복문을 쓸 경우 가장 안쪽의 반복문부터 작동하기 때문에 3번째 카드가 9까지 모두 선택되었다면 2번 반복문이 +1 되고, 2번 반복문에서도 카드가 모두 선택됐다면 1번 반복문도 +1되어 다시 반복된다. 정확한 작동 방식은 디버깅으로 확인해 본다. 그래도 이해가 안 된다면 다중 반복문이 어떻게 작동하는지 확인하는 게 좋다.

3중 반복문을 사용하기 때문에 이 알고리즘의 시간 복잡도는 O(N^3)이 된다. 최대 100이기 때문에 최악의 경우 이 코드는 100만 번의 연산을 수행하게 된다. 그래도 충분히 빠르게 작동해서 문제를 풀 수 있다.