10870번: 피보나치 수 5

문제 출처 : https://www.acmicpc.net/problem/10870

 

언어 : Kotlin

 

문제 설명 :

피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

• 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.
• 첫째 줄에 n번째 피보나치 수를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
10	55

풀이 : 

import java.io.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    bw.write("${fibonacci(br.readLine().toInt())}")
    bw.flush()
    bw.close()
}

fun fibonacci(n: Int) = run {
    tailrec fun fibonacciAcc(n: Int, a: Long, b: Long): Long {
        return when (n == 0) {
            true -> b
            false -> fibonacciAcc(n - 1, a + b, a)
        }
    }
    fibonacciAcc(n, 1, 0)
}

재귀 함수 사용시 다음과 같다.

Kotlin에는 tailrec이라는 키워드가 존재한다. tailrec은 꼬리재귀(tail recurisve)라는 의미로 추가적인 연산 없이 자신 스스로 재귀적으로 호출하다가 값을 리턴하는 함수를 의미한다. 자신만 반복적으로 호출하여 while문과 같이 루프를 사용하는 코드로 변환이 가능하다.

 

이는 곧 재귀함수가 호출되며 소비하는 스택을 아낄 수 있게 된다는 것이고, 루프는 동일한 결과를 출력하며 재귀함수보다 더 적은 자원을 사용하는 것이다.

 

좀 더 세부적인 내용은 다음 주소를 참고하면 좋다.

https://codechacha.com/ko/kotlin-tailrect/

Kotlin - tailrec(꼬리재귀)에 대해서 알아보기

 

 

import java.io.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val arr = (1 .. br.readLine().toInt()).map { it }.toIntArray()
    bw.write("${arr.fold(0) { acc, i -> acc + i }}")
    bw.flush()
    bw.close()
}

재귀함수가 아닌 스트림을 통해서도 간단히 작성할 수 있다.