백준 14888번: 연산자 끼워넣기 (Kotlin)

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

14888번: 연산자 끼워넣기

프로세스

1. 완전 탐색을 떠올린다. 연산자 4개, 자리는 10개이므로 시간 복잡도(경우의 수)는 4^10 = 1,048,576이다.
2. 재귀 함수를 사용한다.
   1. calculate(왼쪽 피연산자(operand), 오른쪽 피연산자를 가리킬 인덱스)로 구성한다.
   2. 마지막 인덱스까지 계산할 때마다 최대 값, 최소 값을 갱신한다.
   3. 각 연산자마다 operand와 현재 피연산자를 계산해서 재귀함수를 호출한다.

풀이

어렵지 않았지만 재귀 함수를 연습하기 좋았다.

 

가장 먼저 완전 탐색을 떠올릴 수 있는데, 연산자 들어갈 자리가 최대 10자리이고 연산자가 4개 뿐이다. 따라서 모든 자리에 연산자를 한 번씩 넣어서 모든 경우의 수를 확인할 경우 4^10 = 1,048,576개 라서 충분히 완전 탐색으로 해결할 수 있다.

재귀 함수

재귀 함수 구성은 배열 1 2 3 4 5 6이 있다고 가정했을 때, (1 2) (연산자) (3 4 5 6)와 같이 나눌 수 있다. 즉, 지금까지 계산한 왼쪽 피연산자와 배열의 나머지에서 그 다음에 계산할 숫자의 현재 인덱스를 인자로 갖게 한다.

fun calculate(operand1: Int, idx: Int)

그리고 인덱스가 마지막 인덱스를 넘으면 전부 계산한 것이기 때문에 최대 값, 최소 값과 비교하여 정답을 갱신한다.

if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

종료 조건이 아니라면, 각 연산자마다 계산해서 다음 자리에 해당하는 연산자를 넣어보기 위해 재귀 함수를 호출한다.

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

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max
import kotlin.math.min

lateinit var numbers: IntArray
lateinit var operators: IntArray // +, -, *, /
var maxValue = Int.MIN_VALUE
var minValue = Int.MAX_VALUE

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    numbers = with(StringTokenizer(readLine())) {
        IntArray(size) { this.nextToken().toInt() }
    }
    operators = with(StringTokenizer(readLine())) {
        IntArray(4) { this.nextToken().toInt() }
    }

    calculate(numbers[0], 1)

    println(maxValue)
    println(minValue)
}

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

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

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }
}