[BaekJoon] 14888번 연산자 끼워넣기 (Kotlin) 문제 풀이 [Silver 1]

문제

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

어떻게 풀 것인가?

문제를 찬찬히 읽어보자.

2가지의 방법이 떠오른다. 1. 브루트 포스, 2. 백트래킹

여기서 시간복잡도를 떠올려보자.

 

연산자는 4개이고, 주어질 수 있는 수는 10개이다.

4^10 = 1,048,576

즉, 아무리 최악이어도 1초는 넘기지 않는다.

 

그래서 브루트 포스보다는 백트래킹을 연습하기 위해서 백트래킹으로 접근하였다.

 

풀면서 놓쳤던점

X

이 문제를 통해 얻어갈 것

재귀, 백트래킹의 기본 사용법

내 코드 

package baekjoon.BJ_14888

import java.util.StringTokenizer
import kotlin.math.max
import kotlin.math.min

// 백준알고리즘 14888번 연산자 끼워넣기
private lateinit var int_arr: IntArray
private lateinit var cal_arr: IntArray // +, -, *, /
private var maxValue = Int.MIN_VALUE
private var minValue = Int.MAX_VALUE

fun main() = with(System.`in`.bufferedReader()) {
    val num = readLine().toInt()
    int_arr = with(StringTokenizer(readLine())) {
        IntArray(num) { this.nextToken().toInt() }
    }
    cal_arr = with(StringTokenizer(readLine())) {
        IntArray(4) { this.nextToken().toInt() }
    }
    backTracking(int_arr[0], 1)

    println(maxValue)
    println(minValue)

}

private fun backTracking(operand1: Int, idx: Int) {
    if (idx >= int_arr.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

    for (i in cal_arr.indices) {
        if (cal_arr[i] <= 0) continue

        cal_arr[i]--
        when (i) {
            0 -> backTracking(operand1 + int_arr[idx], idx + 1)
            1 -> backTracking(operand1 - int_arr[idx], idx + 1)
            2 -> backTracking(operand1 * int_arr[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    backTracking(-(-operand1 / int_arr[idx]), idx + 1)
                } else {
                    backTracking(operand1 / int_arr[idx], idx + 1)
                }
            }
        }
        cal_arr[i]++
    }
}

참고

X