[Algorithm] 백준 - 14888번 연산자 끼워넣기 (Swift)

문제 소개

숫자의 배열과 연산기호의 배열을 주면 이를 통해 가장 큰 값, 작은 값을 찾는 문제이다.

문제 풀이

순서대로 연산을 해주기 때문에 dfs로 앞에서부터 처리하면 되겠다라고 생각했고, 결과는 20ms 로 매우 빠르게 결과값을 얻을 수 있었다. 모든 경우의 수를 계산해준 뒤 maxValue, minValue 를 업데이트 시켰다.

import Foundation

let n = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map { Int($0)! }
let operation = readLine()!.split(separator: " ").map { Int($0)! }

var maxValue = -1_000_000_000
var minValue = 1_000_000_000

func dfs(_ current: Int, _ operation: [Int], _ depth: Int) {
    if depth == n-1 {
        maxValue = max(maxValue, current)
        minValue = min(minValue, current)
    }
    
    var operation = operation
    
    for i in 0..<4 {
        if operation[i] > 0 {
            operation[i] -= 1
            
            switch i {
            case 0: dfs(current+nums[depth+1], operation, depth+1)
            case 1: dfs(current-nums[depth+1], operation, depth+1)
            case 2: dfs(current*nums[depth+1], operation, depth+1)
            case 3: dfs(current/nums[depth+1], operation, depth+1)
            default: return
            }
            
            operation[i] += 1
        }
    }
}

dfs(nums[0], operation, 0)
print(maxValue)
print(minValue)