[백준] 연산자 끼워넣기 (14888)

문제 설명

백준 14888번 문제 링크

입력 및 출력

» 입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, …, AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

» 출력

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

예제 입출력(테스트케이스)

입력	출력
2 5 6 0 0 1 0	30 30
3 3 4 5 1 0 1 0	35 17
6 1 2 3 4 5 6 2 1 1 1	54 -24

문제 힌트

세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다. 최댓값: 1-2÷3+4+5×6 최솟값: 1+2+3÷4-5×6

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ14888_SWIFT
//
//  Created by choiyoujun on 2022/02/18.
//

let N = Int(readLine()!)!
let NUM = readLine()!.split(separator: " ").map { Int($0)! }
var OP = readLine()!.split(separator: " ").map { Int($0)! }
var mininum = 1_000_000_000
var maximum = -1_000_000_000

func dfs(num: Int, depth: Int) -> Void {
    if depth >= N {
        mininum = min(mininum, num)
        maximum = max(maximum, num)
        return
    }

    for i in 0..<4 {
        if OP[i] > 0 {
            OP[i] -= 1

            switch i {
            case 0:
                dfs(num: num + NUM[depth], depth: depth + 1)
            case 1:
                dfs(num: num - NUM[depth], depth: depth + 1)
            case 2:
                dfs(num: num * NUM[depth], depth: depth + 1)
            default:
                dfs(num: num / NUM[depth], depth: depth + 1)
            }

            OP[i] += 1
        }
    }
}

dfs(num: NUM[0], depth: 1)
print(maximum)
print(mininum)