[백준] 1541 (잃어버린 괄호)

#1 알고리즘

#1-1 하향식 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

하향식 동적 프로그래밍을 구현해 풀었다. Caching을 위한 객체로 HashMap<String, Int>를 사용했다. 예를 들어, 1 + 2 + 3 - 4 + 5 - 6 + 7라는 수식을 Caching하기 위해 makeListToKey()라는 함수를 만들었다 (#2 참조). 수식 makeListToKey()에 넣으면 "+1+2+3-4+5-6+7"와 같은 String 객체로 반환되고, 이 String의 값을 Map의 Key로 사용했다.

 

#1-2 '괄호를 친다'는 것의 의미

괄호의 영향으로 각 수의 부호를 바꾸는 작업을, #2의 코드에서 braketize()라는 함수로 구현했다.

 

#2 코드 - 코틀린

package exam1541.ver8_stable

val caching = HashMap<String, Int>()

fun main() {
    val numberList = parseNumbers(readln())
    println(findMinSum(numberList))
}

fun findMinSum(numberList: MutableList<Int>): Int {
    val braketizedList = braketize(numberList)

    return minOf(
        recursive(numberList),
        recursive(braketizedList)
    )
}

fun recursive(numberList: MutableList<Int>): Int {
    if (numberList.isEmpty()) {
        return 0
    }

    val listKey = makeListToKey(numberList)
    if (caching[listKey] != null) {
        return caching[listKey]!!
    }

    val subList = numberList.subList(1, numberList.size)
    val braketizedSubList = braketize(subList)

    val minSum = minOf(
        numberList[0] + recursive(subList),
        numberList[0] + recursive(braketizedSubList)
    )

    caching[listKey] = minSum
    return minSum
}

fun makeListToKey(numberList: MutableList<Int>): String {
    var result = ""

    for (number in numberList) {
        result += if (number >= 0) {
            "+$number"
        } else {
            "$number"
        }
    }

    return result
}

fun parseNumbers(input: String): ArrayList<Int> {
    val numbers = ArrayList<Int>()

    var temp = ""
    for (char in input) {
        if (char == '+' || char == '-') {

            if (temp != "") {
                numbers.add(temp.toInt())
            }
            temp = char.toString()

        } else {
            temp += char
        }
    }

    if (temp != "") {
        numbers.add(temp.toInt())
    }

    return numbers
}

fun braketize(input: MutableList<Int>): MutableList<Int> {
    if (input.isEmpty()) {
        return input
    }

    val result = ArrayList<Int>()

    val isFirstElementMinus = input[0] < 0
    if (isFirstElementMinus) {
        for (i: Int in input.indices) {
            if (i == 0) {
                result.add(input[i])
            } else {
                result.add(-input[i])
            }
        }

    } else {
        for (i: Int in input.indices) {
            result.add(input[i])
        }
    }

    return result
}