백준 1003번 피보나치 함수(Kotlin)

이번 글에선 백준 1003번을 풀어보도록 하자.

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

자세한 문제 내용은 위 링크에서 직접 확인해보도록 하자.

 

풀이

---

이 문제를 보고 제일 먼저 든 풀이법은 그냥 문제에 나온 함수를 돌리는 거였다.

import java.util.Scanner

var zero = 0
var one = 0

fun main(){
    val input = Scanner(System.`in`)
    val t = input.nextInt()

    for(i in 1 .. t){
        var n = input.nextInt()
        fibonacchi(n)
        println("${zero} ${one}")
        zero = 0 ; one = 0
    }
}

fun fibonacchi(n: Int): Int{
    if(n == 0){
        zero++
        return 0
    }else if(n == 1){
        one++
        return 1
    }else
        return fibonacchi(n-1) + fibonacchi(n-2)
}

문제에 쓰여있는 재귀 함수를 돌려서 0과 1일 때마다 카운팅 해서 출력하도록 날로 먹으려 했는데...

당연하게도 시간 초과가 나와버려서 틀리게 됐다.

재귀 함수의 경우 단순 반복문(for문 등)보다 시간이 더 걸리는 점을 감안하면 당연한 결과일 거다.

 

그럼 어떻게 해야 할까...

아래 그림을 한 번 보자.

문제에 나와있는 입력 6을 그림으로 한 번 그려봤다.

재귀 함수를 사용하면 위와 같이 이진트리 같은 모양으로 쭉 내려가게 되는데,

여기서 주목할 점은 각 숫자의 개수이다.

 

숫자들을 보면 6/5/4,4/3,3,3/2,2,2,2,2/1,1,1,1,1,1,1,1/0,0,0,0,0

각 숫자들은 1, 1, 2, 3, 5, 8, 5개만큼 등장한다.

어디서 많이 본 수열인 것 같다는 생각이 들지 않나?

그렇다, 이건 그냥 피보나치 수열이다.

 

즉, F(6)을 재귀 함수로 돌렸을 때, 각 숫자의 개수는

다시 높은 숫자부터 역순으로 맨 처음 0을 뺀 피보나치수열을 만들게 된다.

 

또한 여기서 중요한 점은 0은 2가 나왔을 때 하나만 갈라져 나오기 때문에 "0의 개수 = 2의 개수"가 된다.

따라서 F(n)의 1과 0의 개수를 구하고 싶으면, 그냥 F(n)과 F(n-1)을 구하면 되는 문제였다.

 

그럼 코드로 작성해보도록 하자.

import java.util.Scanner

fun main(){
    val input = Scanner(System.`in`)
    val t = input.nextInt()
    
    for(i in 1 .. t){
        val n = input.nextInt()
        println("${fibonacchi(n-1)} ${fibonacchi(n)}")
    }
}

fun fibonacchi(n: Int): Int{
    if(n == 0) return 0
    if(n == 1) return 1
    var a = 0
    var b = 1
    var tmp = 0
    for(i in 2 .. n){
        tmp = a
        a = b
        b = tmp + b
    }
    return b
}

피보나치수열을 반복문으로 구하는 함수 fibonacchi를 선언하고,

이에 n과 n-1을 argument로 주어서 답을 구하면 시간 초과도 없이 깔끔하게 답이 구해진다.