백준 16637 괄호 추가하기 Kotlin (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

오랜만에 하는 코틀린 PS라 리팩토링이 필요한 코드이다.

풀이에 앞서 주의할 점은, 결과의 최댓값을 저장할 answer 변수의 초깃값을 0으로 설정하면, 최댓값이 음수일 수도 있기 때문에 틀릴 것이고, 결괏값의 범위는 Int범위를 초과하므로, answer의 초깃값을 Long범위의 음수로 잘 설정해야 한다.

본인은 완전 탐색 기반 백트래킹으로 풀었다.

 

기호와 숫자를 나누어 저장하면 다음과 같다.

chArr = {+, *, -, *}

LongArr = {3, 8, 7, 9, 2}

문제의 조건에서 괄호는 하나의 수식만 포함해야 하므로,

위에서 괄호를 치는 경우는

+

*

-

*

+, -

*, *

총 6개의 경우가 나올 수 있다.

즉 기호들을 기준으로 dfs를 하는데,

이전 기호에 괄호를 쳤다면 현재 기호는 스킵하는 것으로 가지치기할 수 있고, 이는 visited 배열을 두어, 괄호 친 기호를 true 처리해 주고, LongArr[i]와 LongArr[i+1]에 chArr[i]의 기호로 연산을 하고, 연산의 값을 LongArr[i+1]에 저장하여 괄호 친 부분만 먼저 계산을 해놓는다.

 

이렇게 괄호를 치는 모든 경우를 탐색하며, 각 경우마다 값들을 모두 더해서 최댓값을 찾으면 된다.

이 부분은, 

만약 위의 예제에서 chArr[0]을 실행할 땐,

LongArr[0] + LongArr[1] // 3 + 8이고,

chArr[1]에 괄호를 친 상태라면

LongArr[0] + LongArr[2] // 3+ 56이다.

코드

import kotlin.math.*

val visited = BooleanArray(10)
val chArr = ArrayList<Char>()
var answer : Long =-99999999999999
fun cal(ch : Char, a : Long, b: Long):Long{
    if(ch=='+'){
        return a+b
    }
    else if(ch=='-'){
        return a-b
    }
    else{
        return a*b
    }
}

fun dfs(intArr : ArrayList<Long>, idx : Int){
    var result=0
    val intArrCopy= LongArray(intArr.size)
    for(i in intArr.indices){
        intArrCopy[i] =intArr[i]
    }

    for(i in chArr.indices){
        if(visited[i])continue
        if(i+1 in chArr.indices &&visited[i+1]){
            intArrCopy[i+2] = cal(chArr[i],intArrCopy[i],intArrCopy[i+2])
            continue
        }
        intArrCopy[i+1]= cal(chArr[i], intArrCopy[i], intArrCopy[i + 1])
    }

    answer = max(intArrCopy[intArrCopy.size-1],answer)
    var i = idx
    while(i in chArr.indices){
        if(i-1>=0 && visited[i-1]) {
            i++
            continue
        }
        val temp = intArr[i+1]
        intArr[i+1]=cal(chArr[i],intArr[i],intArr[i+1])
        visited[i]=true
        dfs(intArr,i+1)
        intArr[i+1] = temp
        visited[i]=false
        i++
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val input = br.readLine()
    val intArr = ArrayList<Long>()

    for(i in input.indices){
        if(input[i].isDigit()){
            intArr.add(Character.getNumericValue(input[i]).toLong())
        }
        else{
            chArr.add(input[i])
        }
    }
    dfs(intArr, 0)
    write("$answer")
    close()
}