백준 14888번 연산자 끼워넣기 - 스위프트(Swift) 풀이

 

---

 

1. 앞에서부터 차례로 연산자를 정한다.
2. 다음 연산자를 고를 때는 남은 연산자 중에 하나를 고른다.
3. N-1개의 연산자를 다 골라서 완성했으면 결과값을 가지고 최대, 최솟값을 갱신한다.

 

1. 앞에서부터 차례로 연산자를 정한다.

 N이 최대 11로 매우 작다. 연산자 개수는 최대 N-1 = 10개이므로, 10가지 종류의 연산자가 있다고 하더라도 모든 경우의 수가 10! 밖에 되지 않는다. 따라서 브루트 포스로 N-1개 연산자를 줄 세우는 모든 경우를 고려해주어도 시간 안에 통과가 가능하다. 앞에서부터 차례로 연산자를 정해주자.

 

2. 다음 연산자를 고를 때는 남은 연산자 중에 하나를 고른다.

 operators[i]를 남아있는 연산자 i의 개수, bruteForce(index, currentValue)를 현재까지의 계산 값이 currentValue이고 index번째 연산자를 정할 차례에 호출하는 함수라고 하자. 각 연산자의 남은 개수를 보고 index번째 연산자가 될 수 있는 모든 경우를 고려해줄 것이다.

 즉, i=0~3까지 순회하면서 operators[i] > 0이라면 해당 연산자가 남아있는 것이므로 해당 연산자를 index번째 연산자로 취할 수 있다. currentValue와 A[index+1]를 해당 연산자로 계산해 newValue를 얻는다.

 이제 연산자 i를 사용했으므로, operators[i]를 1 감소시켜주고 bruteForce(index+1, newValue)를 호출한다. 호출 완료 후에는 다시 operators[i]를 1 증가시켜주어 원상 복구한다.

 

3. N-1개의 연산자를 다 골라서 완성했으면 결과값을 가지고 최대, 최솟값을 갱신한다.

 index = N-1이면 N-1개의 연산자를 완성한 것이므로 이때가 재귀호출의 기저 사례이며, 이때의 currentValue가 전체 계산 결과가 된다. currentValue를 가지고 최대, 최소값을 갱신하고 return 해준다.

반응형

---

import Foundation

var N = 0
var A = [Int]()
var operators = [Int]()
var maxResult = -1_000_000_001
var minResult = 1_000_000_001

// 현재까지의 계산값이 currentValue이고 index번째 연산자를 정할 차례
func bruteForce(index: Int, currentValue: Int) {
    if index == N-1 {
        maxResult = max(maxResult, currentValue)
        minResult = min(minResult, currentValue)
        return
    }
    
    for i in 0..<4 {
        guard operators[i] > 0 else { continue }
        
        operators[i] -= 1
        
        var newValue = currentValue
        switch i {
        case 0:
            newValue += A[index+1]
        case 1:
            newValue -= A[index+1]
        case 2:
            newValue *= A[index+1]
        case 3:
            newValue /= A[index+1]
        default:
            break
        }
        bruteForce(index: index+1, currentValue: newValue)
        
        operators[i] += 1
    }
}

func solution() {
    N = Int(readLine()!)!
    A = readLine()!.split(separator: " ").map{ Int(String($0))! }
    operators = readLine()!.split(separator: " ").map{ Int(String($0))! }
    
    bruteForce(index: 0, currentValue: A[0])
    
    print(maxResult)
    print(minResult)
}

solution()