[Kotlin] 백준 9461 : 파도반 수열

문제 링크

9461번: 파도반 수열

---

---

문제 해설

문제의 제목인 파도반 수열(Padovan sequence)은 Richard Padovan의 이름을 따서 명명된 수열이다. 문제의 그림은 파도반 수열을 나타내는 대표적인 그림 중 하나인데, \(n\)번째 정삼각형의 변의 길이를 \(P(n)\)이라고 할 때 \(P(4)\)부터는 아래와 같이 나타낼 수 있다.

• \(P(4)=2=1+1=P(1)+P(2)\)
• \(P(5)=2=1+1=P(2)+P(3)\)
• \(P(6)=3=1+2=P(3)+P(4)\)
• \(P(7)=4=2+2=P(4)+P(5)\)
• \(P(8)=5=2+3=P(5)+P(6)\)
• \(P(9)=7=3+4=P(6)+P(7)\)
• \(P(10)=9=4+5=P(7)+P(8)\)
• \(P(11)=12=5+7=P(8)+P(9)\)
• \(P(12)=16=7+9=P(9)+P(10)\)
• ...

즉, 파도반 수열은 \(4\leq n\)인 \(n\)에 대해서 \(P(n)=P(n-3)+P(n-2)\)가 성립하게 된다. 이를 이용하여 100까지의 파도반 수열을 구해놓은 후 각 테스트 케이스에 맞는 값을 꺼내오기만 하면 된다.

 

단, \(P(79)\)부터 Int의 범위를 초과하기 때문에 Long타입을 사용해야 한다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val array = LongArray(101)
    array[1] = 1L
    array[2] = 1L
    array[3] = 1L
    for (i in 4..100) {
        array[i] = array[i - 2] + array[i - 3]
    }
    repeat(readLine().toInt()) {
        bw.write("${array[readLine().toInt()]}\n")
    }
    bw.close()
}

---

참조 링크

Padovan sequence - Wikipedia