[백준] 9184번 신나는 함수 실행

9184번 신나는 함수 실행

접근방법

재귀로 푸는 방식은 콜스택이 너무 많이 쌓이고 큰 수가 여러 번 나오면 시간이 초과될 것이 분명했다.

하지만 문제에서 주어진 조건을 분석했을 때, 숫자는 -50 <= a <= 50이였지만 실제로 필요로 하는 값은 0<= a <=20였다.

따라서 각 조건에 따라서 주어진 키값을 계산할 때 20을 초과하면 20으로 낮추고 0이하이면 0으로 바꿔주는 작업을 추가하였다

그리하여서 21개의 숫자만 고려하면 되었고 21^3개의 키를 갖는 map을 만들어서 Key값과 값을 저장하도록 하였다.

클래스 생성시에 DP를 위해 값을 미리 만들어 놓았고 입력이 들어오면 값을 출력하는 방식으로 문제를 풀었다.

시간복잡도

삽입: O(21^3)
조회: O(1)

공간복잡도

O(21^3)

Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.BufferedWriter
import java.io.OutputStreamWriter

class IO9184 {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private val bw = BufferedWriter(OutputStreamWriter(System.out))

    fun flush() = bw.flush()
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)

    fun getIntList() = br.readLine().split(" ").map { it.toInt() }
}

fun main() {
    val io = IO9184()
    val check = { numList: List<Int> -> (numList.count { it == -1 } == 3) }
    val w = W()
    while (true) {
        val numList = io.getIntList()
        when (check(numList)) {
            true -> {
                break
            }
            false -> {
                val message = "w(${numList[0]}, ${numList[1]}, ${numList[2]}) = "
                io.write(message + w.find(numList) + "\n")
            }
        }
    }
    io.flush()
    io.close()
}

class W {
    val map = hashMapOf<List<Int>, Long>()

    init {
        (0..20).forEach { a ->
            (0..20).forEach { b ->
                (0..20).forEach { c ->
                    val key = listOf(a,b,c)
                    map[key] = dp(key)
                }
            }
        }
    }

    private fun dp(key: List<Int>): Long {
        val newKey = convertKey(key)
        if (map.containsKey(newKey)) {
            return map[newKey]!!
        }
        val (a,b,c) = newKey
        return when {
            a <= 0 || b <= 0 || c <= 0 -> {
                1
            }
            a > 20 || b > 20 || c > 20 -> {
                dp(listOf(20,20,20))
            }
            b in (a + 1) until c -> {
                dp(listOf(a, b, c-1)) + dp(listOf(a, b-1, c-1)) - dp(listOf(a, b-1, c))
            }
            else -> {
                dp(listOf(a-1, b, c)) + dp(listOf(a-1, b-1, c)) + dp(listOf(a-1, b, c-1)) - dp (listOf(a-1, b-1, c-1))
            }
        }
    }

    private fun convertKey(key: List<Int>): List<Int> {
        val countUnder0 = key.count { it <= 0 }
        val countOver20 = key.count { it > 20 }
        return if (countUnder0 > 0) {
            listOf(0,0,0)
        }else if (countOver20 > 0 ) {
            listOf(20,20,20)
        } else {
            key.map {
                if (it < 0) 0
                else it
            }
        }
    }

    fun find(key: List<Int>): Long {
        return map[convertKey(key)]!!
    }
}