[Kotlin][Algorithm] 2749 - 피보나치 수 3

문제 요약

문제는 간단하다 그냥 피보나치 수를 계산하는 문제이다.
하지만 구해야 하는 피보나치 수인 n이 1,000,000,000,000,000,000보다 작거나 같은 자연수라는 것이 이 문제의 어려운 점이다.

문제 접근

이전에 피보나치 문제는 보통 피보나치의 중간 계산값이 커지는 것을 문제에서 주어진 나머지 값으로 모듈러 연산을 통해 계산하면 풀리던 문제이지만 해당 문제는 n이 매우 큰수이기 때문에 정직하게 n만큼 계산하면 시간초과가 뜬다.

그럼 어떻게 n 만큼 계산하지 않고 피보나치 n의 값을 구할 수 있을까?

파사노 주기

피사노 주기(Pisano Period)는 피보나치 수열을 어떤 수 M으로 나눈 나머지가 반복되는 주기를 말한다.
즉, 피보나치 수를 같은 값으로 나눌때 반복되는 패턴이 있다는 것이다. 패턴이 있다는 것은 n 만큼 정직하게 계산을 안해도 된다는 것
이 반복되는 패턴의 길이를 피사노 주기라고 한다.

예를 들어 M = 2일때, 피보나치 수열을 2로 나눈 나머지는 '0, 1, 1, 0, 1, 1, ...' 와 같이 3의 주기로 반복된다 따라서 M =2 의 피사노 주기는 3인 것이다.

다른 예로, M = 3일 때의 피보나치 수열을 3으로 나눈 나머지는 '0, 1, 1, 2, 0, 2, 2, 1, 0, ...' 와 가이 8의 주기로 반복된다. 따라서 M = 3 의 피사노 주기는 8인 것이다.

파사노 주기 구하는 법

그냥 간단하게 생각하면 된다.
M으로 나눈 나머지를 계산하면서 0과 1로 되돌아 오는 순간을 찾는 것이다.

피보나치 수열은 이전 두 값을 통해 결정된다.
그러니 0과 1이 연속적으로 나왔다면 그 이후 값은 초기와 동일하게 진행된다. 즉 0과 1이 나온 순간 그 지점이 파사노의 주기인 것이다.

코드

const val MOD = 1000000

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toLong()
	
    // null이면 n까지 반복되는 주기가 없다. 그냥 그대로 n 구하면 된다.
    var pisanoPeriod = calculatePisano(n) ?: (n + 1)
    val nModePisano = n % pisanoPeriod

    println(fibonacci(nModePisano))
}

/**
 * 피사노 주기는 피보나치 수열을 어떤수 M으로 나눈 나머지가 반복되는 주기
 * 처음 두항인 0과 1로 오는 곳 찾으면 됌
 */
fun calculatePisano(n: Long): Long? {
    var prePre = 0L
    var pre = 1L

    for (i in 2 until n) {
        val now = (prePre + pre) % MOD
        prePre = pre
        pre = now
        if (prePre == 0L && pre == 1L) return i - 1
    }

    return null
}

fun fibonacci(n: Long): Long {
    if (n <= 1L) return n

    var prePre = 0L
    var pre = 1L
    for (i in 2 .. n) {
        val now = (prePre + pre) % MOD
        prePre = pre
        pre = now
    }

    return pre
}

배운점

1. 피사노 주기 : 피보나치 수열이 모듈로 연산을 통해 어떤 수 M으로 나눈 나머지를 취했을 때 나타나는 주기적 패턴

2. 계산 해야할 수가 매우 크다면 어떤 패턴이 있지 않을까 생각해보기