[BOJ] 14888번 : 연산자 끼워넣기

문제 보기

소스

kotlin

import java.util.Scanner
import kotlin.math.*

var n = 0
var min = Int.MAX_VALUE
var max = Int.MIN_VALUE
lateinit var nums: IntArray
lateinit var visit: BooleanArray
lateinit var opers: MutableList<String>

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    nums = IntArray(n)
    visit = BooleanArray(n - 1)
    opers = mutableListOf()

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

    repeat(nextInt()) { opers.add("+") }
    repeat(nextInt()) { opers.add("-") }
    repeat(nextInt()) { opers.add("*") }
    repeat(nextInt()) { opers.add("/") }

    dfs("")

    println(max)
    println(min)
}

fun dfs(comb: String) {
    if (comb.length == n - 1) {
        min = min(min, comb.result())
        max = max(max, comb.result())
        return
    }

    for (i in 0 until n - 1) {
        if (visit[i]) continue
        visit[i] = true
        dfs(comb + opers[i])
        comb.removeRange(comb.length - 1, comb.length - 1)
        visit[i] = false
    }
}

fun String.result(): Int {
    var temp = nums[0]
    for (i in 0 until n - 1) {
        temp = calc(temp, nums[i+1], this[i])
    }
    return temp
}

fun calc(a: Int, b: Int, c: Char): Int {
    return when (c) {
        '+' -> a + b
        '-' -> a - b
        '*' -> a * b
        '/' -> a / b
        else -> 0
    }
}

메모리	시간
304432 KB	1548 ms

import java.util.Scanner
import kotlin.math.*

var n = 0
var min = Int.MAX_VALUE
var max = Int.MIN_VALUE
val opers = IntArray(4)
lateinit var nums: IntArray
lateinit var visit: BooleanArray

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    nums = IntArray(n)
    visit = BooleanArray(n - 1)

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

    for (i in 0 until 4) {
        opers[i] = nextInt()
    }

    dfs(nums[0], 1)

    println(max)
    println(min)
}

fun dfs(acc: Int, count: Int) {
    if (count == n) {
        min = min(min, acc)
        max = max(max, acc)
        return
    }

    for (i in 0 until 4) {
        if (opers[i] <= 0) continue
        opers[i]--
        dfs(calc(acc, nums[count], i), count + 1)
        opers[i]++
    }
}

fun calc(a: Int, b: Int, oper: Int): Int {
    return when (oper) {
        0 -> a + b
        1 -> a - b
        2 -> a * b
        3 -> a / b
        else -> 0
    }
}

메모리	시간
13684 KB	140 ms