[Algorithm] 백준 - 16639번 괄호 추가하기3

🤓 문제

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

🧙 풀이과정

우선 아래의 문제와 비슷하고, 이번에는 괄호를 아무렇게나 씌울 수 있다는 조건이 추가되었다.

[Algorithm] 백준 - 16638번 괄호 추가하기2 (Swift)

✨ 첫 번째 풀이 (단순하게)

첫 번째는 아주 간단하게 접근했다. 그냥 모든 경우를 계산했다. 

let n = Int(readLine()!)!
let expression = Array(readLine()!).map { String($0) }

func operate(_ array: [String]) -> String {    
    let first = Int(array[0])!
    let last = Int(array[2])!

    switch array[1] {
    case "*": return String(first * last)
    case "+": return String(first + last)
    case "-": return String(first - last)
    default: return "error"
    }
}

var answer = Int.min

func calculate(_ array: [String]) {
    let count = array.count
    
    if count == 1 {
        answer = Int(array[0])!
    }
        
    if count == 3 {
        let cal = operate(array)
        answer = max(answer, Int(cal)!)
        return
    }

    for i in stride(from: 0, to: count - 1, by: 2) {
        let cal = operate(Array(array[i...i+2]))
        let left = i-1 > 0 ? Array(array[0...i-1]) : []
        let right = i+3 < count ? Array(array[i+3...count-1]) : []
        calculate(left + [cal] + right)
    }
}

calculate(expression)

print(answer)

 

결과는 아래와 같이 나왔는데 주어진 배열이 1인 경우를 고려하지 못해서 약간의 우여곡절이 있었다. 이 풀이는 살짝 아쉬웠는데 시간이 412ms로 성능이 아쉬웠다.

✨ 두 번째 풀이 (DP)

이렇게 모든 경우의 수를 고려하며 풀 수밖에 없는 걸까? 고민하다가 (아래의 힌트를 보고...) 다이내믹 프로그래밍으로 풀어보고자 했다. 왜냐하면 결국 수식은 "숫자 연산 숫자" 형태인데 최댓값을 얻으려면 양쪽의 최대 최소를 고려해 주며 연산하면 되지 않을까?

• + 인 경우: 최대 + 최대가 최댓값, 최소 + 최소가 최솟값이 될 것이다.
• - 인 경우: 최대 - 최소가 최댓값, 최소 - 최대가 최솟값이 될 것이다.
• * 인 경우: 이부분이 살짝 복잡한데 음수인 경우를 고려해줘야 한다.
  • 최대: 최대 * 최대 혹은 최소 * 최소가 최댓값이 될 것이다.
  • 최소: 최대 * 최소, 최소 * 최대, 최소 * 최소 중에 최솟값을 찾으면 된다.

남은 것은 어떻게 최대, 최소를 저장하고 사용해야 하냐는 문제가 남아있다. dp라는 이차원 배열을 만들고, dp[i][j]에 i부터 j까지의 최대, 최소를 (min: Int, max: Int) 튜플형태로 넣었다. 예를들면 3+8*7-9*2 가 주어진다면 [3, 8, 7, 9, 2]와 ["+", "*", "-", "*"] 로 나눈 후 만약 dp[0][2]라면 3+8*7 의 최댓값, 최솟값을 저장해 놓는 형태이다. 그렇게 된다면 결국 dp[0][4].max 가 최댓값이 될 것이다.

 

양쪽의 값을 가져오는 방법도 dp[0][1]을 계산한다고 한다면 dp[0][0], dp[1][1]을 가져와서 계산해야 한다. 만약에 dp[0][4]를 계산하고 싶다면? dp[0][0], dp[1][4] 와 dp[0][1], dp[2][4] 와 dp[0][2], dp[3][4] 를 계산하여 최대값 최소값을 갱신해주면 된다.

 

결국 연산이 하나 들어간 것 부터 계산해줘서 채워주면 되기 때문에 length 1부터 시작해서 dp를 채워주면 된다!

let n = Int(readLine()!)!
let expression = Array(readLine()!).map { String($0) }

/// 번호 추출
let numbers = expression.compactMap { Int($0) }

/// 연산기호 추출
let operators = expression.enumerated().filter { $0.offset % 2 == 1 }.map { $0.element }

/// 최소는 Int.max, 최대는 Int.min 으로 dp 초기화
var dp = Array(repeating: Array(repeating: (min: Int.max, max: Int.min), count: numbers.count), count: numbers.count)

/// 자기부터 자기까지 연산의 최댓값, 최솟값은 자기 자신
for (i, number) in numbers.enumerated() {
    dp[i][i] = (number, number)
}

/// length는 연산의 길이, 1인 경우 "숫자 연산 숫자", 2인 경우 "숫자 연산 숫자 연산 숫자"
for length in 1..<numbers.count {
    /// i는 시작하는 숫자 지점
    for i in 0..<numbers.count - length {
        let j = i + length

        /// 시작 숫자 지점과 목표 숫자 지점의 중간인 k (자연스럽게 operators의 인덱스)
        for k in i..<j {
            let maxLeft = dp[i][k].max
            let minLeft = dp[i][k].min
            let maxRight = dp[k+1][j].max
            let minRight = dp[k+1][j].min

            var maximum = Int.min
            var minimum = Int.max
            
            /// 최대, 최소 계산, 부호별 케이스 고려
            switch operators[k] {
            case "+":
                maximum = maxLeft + maxRight
                minimum = minLeft + minRight
            
            case "-":
                maximum = maxLeft - minRight
                minimum = minLeft - maxRight
            
            case "*":
                maximum = max(maxLeft * maxRight, minLeft * minRight)
                minimum = min(maxLeft * minRight, minLeft * maxRight, minLeft * minRight)
            
            default: continue
            }

            dp[i][j].max = max(dp[i][j].max, maximum)
            dp[i][j].min = min(dp[i][j].min, minimum)
        }
    }
}

print(dp[0][numbers.count-1].max)

결과는 훨씬 좋게 나왔다. 🥳