[백준/파이썬] 1003번 피보나치 함수 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1003번 피보나치 함수
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

위 피보나치 함수에서, fibonacci(n)이 n번째 피보나치 수를 의미할 때 fibonacci(n)이 호출되면 0, 1이 몇번 출력되는가?

코드

cnt0 = [1, 0]
cnt1 = [0, 1]

for i in range(2, 41):
    cnt0.append(cnt0[i-1]+cnt0[i-2])
    cnt1.append(cnt1[i-1]+cnt1[i-2])
    
for _ in range(int(input())):
    n = int(input())
    print(cnt0[n], cnt1[n])

설명

해당 피보나치 함수는 n<=1인 경우에 1번, 2인경우에 3번, 3인 경우에 4번… 호출되죠.

좀 더 일반적으로 바꿔보면, n-2인 경우 x_n-2, n-1인 경우 x_n-1, 번 일 때, n인 경우 x_n-2 + x_n-1번 호출됩니다.

즉, 해당 함수의 시간복잡도 ~= O( fibonacci( n ) )이 되죠. 이렇게되면 n이 조금만 커져도 수행횟수가 매우 많아집니다.

따라서, 동적 계획법을 이용해야 합니다.

제가 푼 방법에서는 0을 호출한 횟수와 1을 호출한 횟수를 각각 cnt0, cnt1이라는 리스트로 선언하여 메모이제이션으로 씁니다.

cnt0[7]은 fibonacci(7)이 호출되었을 때 0이 사용된 횟수를 의미합니다.

이 리스트 자체는 어떤 n이 와도 사용할 수 있으므로 여러번의 입력이 있더라도 한번만 구하면 됩니다.

이후 테스트 케이스의 수만큼 cnt0[n]과 cnt[1]을 출력해주기만 하면 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---