[BOJ/백준][Silver2] 9184 : 신나는 함수 실행 (Kotlin)

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

9184번: 신나는 함수 실행

 

 

 

[난이도] Silver2
[유형] DP

[풀이]
재귀만을 이용해서 값을 구하게 되면 w(x,y,z)를 중복으로 실행하는 경우가 여러번 생길 수 있으므로
DP[21][21][21] 배열을 선언하여 메모제이션을 해주어야 한다.
DP[x][y][z]에 값이 있으면 이 값을 return해서 더이상 재귀가 수행되지 않도록 한다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*
var dp=Array(21,{Array(21,{Array<Int>(21,{-1})})})
fun sol(n:Int,m:Int,k:Int):Int{
    when {
        (n <= 0 || m <= 0 || k <= 0) -> return 1
        (n > 20 || m > 20 || k > 20) -> return sol(20, 20, 20)
    }
    if(dp[n][m][k]!=-1) return dp[n][m][k]
    dp[n][m][k] = when{
        (n<m&&m<k)->sol(n,m,k-1)+sol(n,m-1,k-1)-sol(n,m-1,k)
        else -> sol(n-1,m,k)+sol(n-1,m-1,k)+sol(n-1,m,k-1)-sol(n-1,m-1,k-1)
    }
    return dp[n][m][k]
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    while(true){
        var (N,M,K) = readLine().split(' ').map{it.toInt()}
        if(N==-1&&M==-1&&K==-1) break
        println("w($N, $M, $K) = ${sol(N,M,K)}")
    }
}

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/9184.cpp