[백준] 9461번 파도반 수열

9461번 파도반 수열

접근 방법

한 변의 가장 긴 길이를 기준으로 추가가 될 때, 이전에 추가된 삼각형 변의 길이와 밑 변의 연장선을 공유하는 삼각형의 길이가 추가된다.
따라서, P[N] = P[N-1] + P[N-5]의 점화식을 얻을 수 있다.

코드

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val testNum = br.readLine().toInt()
    val arr: ArrayList<Long> = arrayListOf()
    arr.add(1)
    arr.add(1)
    arr.add(1)
    arr.add(2)
    arr.add(2)
    
    for (i in 5..100) {
        arr.add(arr[i-1] + arr[i-5])
    }
    repeat(testNum) {
        println(arr[br.readLine().toInt()-1])
    }
}