[BOJ] 2193 이친수

이친수

링크: https://www.acmicpc.net/problem/2193

이친수를 구하기 위해서 n번째 자리에서 이전의 자료를 활용해야겠다고 생각을 했다.
예로 5자리의 이친수 개수를 구하기 위해서는 3자리의 이친수까지 개수를 모두 더한 값과 10000의 1을 더한 값인 5가 된다.
이런 식으로 이전에 구한 데이터들을 활용하고, 각 자리를 왼쪽으로 shift 연산을 하며 구하면 된다고 생각을 했다.

하지만 이를 계속해서 구해보니 특이점을 발견했다.
[1, 1, 2, 3, 5, 8, 13 ..]으로 나아가는 것이 fibonacci 수열 규칙성을 띄는 것을 발견했다.

그래서 경로를 바꾸어 피보나치 수열로 해결을 했다.

이것이 가장 최적의 해결법은 아니라고 생각이 되는데, 더 좋은 방법을 추후 탐구해볼 예정이다.

• 정답 코드

class Boj2193 {
    companion object{
        @JvmStatic
        fun main(args: Array<String>){
            val n = readln().toInt()
            val fibo = Array(n+1,{(0).toBigInteger()})

            if(n == 0) {
                println(0)
                return
            }
            fibo[0] = (0).toBigInteger()
            fibo[1] = (1).toBigInteger()

            for(i in 2..n)
                fibo[i] = (fibo[i-2] + fibo[i-1])

            println(fibo[n])
        }
    }
}