코테 연습 with Kotlin - 6

이번에 풀어본 문제는 백준 14888번 문제이다.

<문제>

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다.
그 후 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.
(연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있으며 , 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행)
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하여라

<특이사항>

연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

<풀이>

문제를 보고 모든 경우의 수를 구하는 백트래킹 문제이구나 싶었다.
그래서 최대와 최소를 담을 수 있는 변수를 만들고, 문제를 풀 재귀함수를 만들었다. 특이사항으로 수는 항상 -10억 <= 수 <= 10억라고 했으므로 최소를 -10억, 최대를 10억으로 초기화하였다. 그리고 계산량을 줄이기 위해 꼬리재귀를 이용하였다.

<코드>

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

fun main() = with(Scanner(System.`in`)){
    var arr = IntArray(100){0} 
    var operators = IntArray(4){0}
    var n = 0
    var max = -100000000
    var min = 100000000


    n = nextInt()


    for (i in 0 until n)
        arr[i] = nextInt()


    for (i in operators.indices)
        operators[i] = nextInt()

    fun operation(count : Int, x : Int){

        if(count == n){
            max = max(max,x)
            min = min(min,x)
        }

        for(i in operators.indices){
            if(operators[i] != 0){
                operators[i]--
                when(i){
                    0 -> operation(count+1,x+arr[count])
                    1 -> operation(count+1,x-arr[count])
                    2 -> operation(count+1,x*arr[count])
                    3 -> operation(count+1,x/arr[count])
                }
                operators[i]++
            }
        }
    }

    operation(1,arr[0])

    println(max)
    println(min)

}