[백준 / BOJ] 24416번 알고리즘 수업 - 피보나치 수 1 (C++, Python)

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

24416번: 알고리즘 수업 - 피보나치 수 1

---

문제

---

문제 풀이

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

코드 1은 return 1이다.

 

그런데 잘 생각해보면 이 피보나치 함수는 1의 합으로 피보나치 수를 구하게 된다. 어차피 숫자는 1밖에 없기 때문에 바로 알아챌 수 있다. 그렇다면 코드 1은 n의 피보나치 수만큼 실행된다.

 

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    return f[n];
}

코드 2는 반복문의 횟수만큼 실행되게 된다. 그런데 1, 2일때는 반복문에 존재하지 않으므로 N - 2만큼 실행된다.

 

큰 틀은 C++이나 파이썬이나 같으므로 이를 그대로 코드로 구현해주면 된다.

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감

솔직히! 코드 1이 얼만큼 실행되는지 바로 알아채지 못했다. 직접 숫자를 넣고 그림으로 그려보다가 알아챘다..