[백준 13699번] [Kotlin] 점화식

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

13699번: 점화식

 

난이도 : 실버 4
태그 : 다이나믹 프로그래밍

 

 

설명

 

규칙성을 찾아 풀이하는게 아닌,

그냥 이전에 구한 값을 사용해 다음 값을 구하는 문제입니다.

 

그냥 점화식을 그대로 소스코드로 옮기면 됩니다.

 

 

소스코드

fun main() {
    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()

    val t = Array(n + 1) { 0L }
    t[0] = 1

    for (i in 1..n)
        for (k in 0 until i)
            t[i] += t[k] * t[i - k - 1]

    println(t[n])
}

 

 

 

후기

당연히 규칙성을 찾아 풀이하는 문제인 줄 알았는데,

규칙성도 딱히 안보이고... 시간 제한도 5초길래

혹시...? 하는 생각에 그냥 점화식을 그대로 썼더니 통과했습니다.

 

이전에 구한 값을 이용한다는 점에서

다이나믹 프로그래밍이긴 하지만, 구현 태그도 들어갔으면 좋겠네요.