[Swift][DP] 백준 10422번 (괄호)

요구능력 : 다이나믹프로그래밍

 

코드설명 : 

 

 

후기 : 상당히 어려운문제 이런생각을 대체 어떻게해서 풀어야하지..

하지만 뭔가 얻어가는듯한 문제이다.

let t = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: 5001)
dp[0] = 1
dp[2] = 1
for n in stride(from: 4, through: 5000, by: 2) {
    for i in stride(from: 2, through: n, by: 2){
        dp[n] += dp[i - 2] * dp[n - i]
        dp[n] %= 1000000007
    }
    
}

for _ in 0..<t{
    let a = Int(String(readLine()!))!
    print(dp[a])
}