[BOJ] 2798번 : 블랙잭

문제 보기

소스

kotlin

import java.util.*
import kotlin.math.max

var n = 0
var m = 0
var result = 0
val nums = IntArray(101)
val visited = BooleanArray(101)

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    for (i in 0 until n) {
        nums[i] = nextInt()
    }

    val arr = mutableListOf<Int>()
    dfs(arr, 0)
    println(result)
}

fun dfs(arr: MutableList<Int>, count: Int) {
    if (count == 3) {
        if (arr.sum() <= m) result = max(result, arr.sum())
        return
    }

    for (i in 0 until n) {
        if (!visited[i]) {
            visited[i] = true
            arr.add(nums[i])
            dfs(arr, count + 1)
            arr.removeAt(arr.size - 1)
            visited[i] = false
        }
    }
}

단순히 3중 for문을 이용하여 간단하게 해결할 수 있는 문제이지만 백트래킹에 익숙해지기 위해 위와 같이 풀이하였다.