[BOJ] 14888

[HyomK]

백준 14888 연산자 끼워넣기
[문제유형] 백트래킹
https://www.acmicpc.net/problem/14888

개선 전 코드 (시간초과)

   data class OP(val id : Int, val operator : Int)
   // 중복 방지를 위해 class 화
    fun backTracking( tmpOp : ArrayList<OP>){
        if(tmpOp.size == tot){
            var result = nums[0]
            for(i in 0 until tmpOp.size){
                when(tmpOp[i].operator){
                    0 ->{ result += nums[i+1]}
                    1 ->{ result -= nums[i+1]}
                    2 ->{ result *= nums[i+1] }
                    3 ->{
                        if( result < 0 && nums[i+1] >= 0){
                            val divider = Math.abs(result)
                            result = divider / nums[i+1]
                        }else{
                            result /= nums[i + 1]
                        }
                    }
                }
            }
            min = Math.min(min, result)
            max = Math.max(max, result)
        }

        for(i in 0 until ops.size){
            if(tmpOp.map{it.id}.contains(ops[i].id)) continue
            tmpOp.add(ops[i])
            backTracking(tmpOp)
            tmpOp.removeLast()
        }
    }

기본적인 순열 방식을 이용해 list 를 넘겨주고 마지막에 리스트를 순회하며 결과 계산하는 방식 -> 시간초과 발생
결과 값만 넘겨도 되는 문제이기 때문에 depth 와 결과 값을 넘겨주도록 한다

개선한 코드

    fun fastBackTracking(depth : Int, tmp : Long){
        if(depth == N){
            min = Math.min(min,tmp)
            max = Math.max(max,tmp)
            return
        }

        for(i in 0 until 4){
            if(operator[i]<=0) continue
            operator[i]--
            when(i){
                0 ->{ fastBackTracking(depth+1, tmp + nums[depth])}
                1 ->{ fastBackTracking(depth+1, tmp - nums[depth])}
                2 ->{ fastBackTracking(depth+1, tmp * nums[depth])}
                3 ->{
                    fastBackTracking(depth+1, tmp / nums[depth])
                }
            }
            operator[i]++
        }
    }