14888번: 연산자 끼워넣기

문제 풀이 아이디어

• 모든 경우의 수를 따져서 완전 탐색해야 합니다.
  • 순열 혹은 dfs를 사용하면 됩니다.
• 대표적인 dfs 문제인 동서남북 이동 문제와 결국 동일한 구조입니다.
  • 동서남북 문제처럼 연산자도 배열에 넣어두고 사용하면 코드가 보기 좋아집니다.

코드

// 연산자 유형 typealias
typealias Operation = (Int, Int) -> Int

// 연산자 4가지 정의 해두기
func add(_ x: Int, _ y: Int) -> Int { x + y }
func substract(_ x: Int, _ y: Int) -> Int { x - y }
func multiply(_ x: Int, _ y: Int) -> Int { x * y }
func devide(_ x: Int, _ y: Int) -> Int { x / y }

// 연산자들의 배열
let operations: [Operation] = [add, substract, multiply, devide]

// 입력 받기
let N = Int(readLine()!)!
let array = readLine()!.split(separator: " ").map { Int(String($0))! }
var numOfOperations = readLine()!.split(separator: " ").map { Int(String($0))! }

// 연산 결과를 저장할 배열
var results = [Int]()

// dfs 구현
func dfs(nowIndex: Int, result: Int) {
    // 현재 index가 N과 같으면 (= 연산 끝)
    if nowIndex == N {
        results.append(result) //👉 결과 배열에 저장하고 리턴
        return
    }
    
    // 연산자 종류 (4개)를 순회하면서
    for i in 0..<4 {
        if numOfOperations[i] != 0 { //👉 아직 연산자가 남아있으면 연산해서 dfs 돌리기
            numOfOperations[i] -= 1
            dfs(nowIndex: nowIndex + 1, result: operations[i](result, array[nowIndex]))
            numOfOperations[i] += 1
        }
    }
}

dfs(nowIndex: 1, result: array[0])

print(results.max()!)
print(results.min()!)