Today I Learned

오늘도 자바 코테 공부!

Count Primes

Leetcode 204번 https://leetcode.com/problems/count-primes/description/

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

• 입력
  1000
• 출력
  517691607

문제 풀이

• 피보나치 수를 일반적인 재귀의 형태로 풀면 지수시간의 시간 복잡도를 가지기 때문에 이를 피하기 위해 행렬 거듭제곱 방법으로 문제를 풀었다.

1. main함수에서는 입력을 toLong()으로 받아주고 피보나치 함수를 호출한다.

2. 피보나치 함수에서는 2x2크기의 행렬을 생성하고 만약 n이 1이하면 그대로 n을 반환하고, 아니면 power 함수를 호출해 행렬의 거듭 제곱을 계산하게 한다.

3. power함수는 주어진 행렬을 거듭제곱해 계산한다. power를 재귀적으로 호출해 n을 절반으로 나눠서 거듭제곱을 계산하고, multiply 함수를 사용해 행렬을 곱한다. 그리고 n이 홀수면 한번 더 행렬을 곱하게 한다. 즉, 주어진 행렬의 n-1 거듭제곱을 계산하여 n번째 피보나치 수를 구하는 과정이다.

4. multiply 함수는 두개의 2x2크기의 행렬을 곱해 결과를 반환한다. 결과는 주어진 문제대로 1000000007로 나눈 나머지만 계산되게 한다. 계산된 결과는 첫번째 행렬에 저장된다. 계산이 끝나면 출력이 되면서 완료!

Java 코드

fun main() {
    val n = readln().toLong()
    println(fibonacci(n))
}

fun fibonacci(n: Long): Long {
    val matrix = arrayOf(longArrayOf(1, 1), longArrayOf(1, 0))
    if (n <= 1) return n
    power(matrix, n - 1)
    return matrix[0][0] % 1000000007
}

fun power(matrix: Array<LongArray>, n: Long) {
    if (n <= 1) return
    power(matrix, n / 2)
    multiply(matrix, matrix)
    val temp = arrayOf(longArrayOf(1, 1), longArrayOf(1, 0))
    if (n % 2 != 0L) multiply(matrix, temp)
}

fun multiply(matrixA: Array<LongArray>, matrixB: Array<LongArray>) {
    val x = (matrixA[0][0] * matrixB[0][0] + matrixA[0][1] * matrixB[1][0]) % 1000000007
    val y = (matrixA[0][0] * matrixB[0][1] + matrixA[0][1] * matrixB[1][1]) % 1000000007
    val z = (matrixA[1][0] * matrixB[0][0] + matrixA[1][1] * matrixB[1][0]) % 1000000007
    val w = (matrixA[1][0] * matrixB[0][1] + matrixA[1][1] * matrixB[1][1]) % 1000000007

    matrixA[0][0] = x
    matrixA[0][1] = y
    matrixA[1][0] = z
    matrixA[1][1] = w
}