[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기

문제

풀이 언어

kotlin

코드

import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*

var n = 0
var max_value = Int.MIN_VALUE
var min_value = Int.MAX_VALUE
lateinit var array: Array<Int>
lateinit var operator: Array<Int>

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    array = Array(n) { nextInt() }
    operator = Array(4) { nextInt() }

    calculate(array[0], 1)
    println(max_value)
    println(min_value)
}

fun calculate(sum: Int, index: Int) {
    if (index == n) {
        max_value = max(sum, max_value)
        min_value = min(sum, min_value)
        return
    }

    for (i in 0..3) {
        if (operator[i] > 0) {
            operator[i]-- // 연산자 줄이고
            when (i) {
                0 -> calculate(sum + array[index], index + 1)
                1 -> calculate(sum - array[index], index + 1)
                2 -> calculate(sum * array[index], index + 1)
                3 -> calculate(sum / array[index], index + 1)
            }
            operator[i]++ // 연산자 다시 돌려놓고
        }
    }
}

풀이 방법

이번 문제는 백트래킹 보다는 DFS 에 가깝다. 둘이 개념적으로 매우 유사하지만 이번 문제의 경우 가지치기 없이 모든 경우에 대해 탐색하고 있기에 DFS라고 판단했다. (operator[i] > 0 조건을 가지치기로 본다면 백트래킹에 해당한다고도 볼 수 있다.)

 

+, -, *, % 연산을 모두 진행하면 된다. 중요한 점은 연산자 개수를 다시 돌려놔야 한다는 것이다.

결과