백준 1003번: 피보나치 함수 [실버 3] - Python

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

1003번: 피보나치 함수

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

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(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

 

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

문제 조건 (0<=N<=40)을 고려하지 않는다면 문제 유형을 재귀로 착각할 수도 있을 것 같습니다. 저도 그랬어요 ^^;

저도 처음엔 '그냥 문제에서 준 함수에다 카운트 변수 두 개 만들어서 횟수 세면 되는 거 아니야??'라고 생각했는데요,

 

시간 초과 코드

import sys
input = sys.stdin.readline

t = int(input())

ns = [int(input()) for _ in range(t)]

def fib(n):
    global cnt0, cnt1
    if n == 0:
        cnt0 += 1
        return 0
    if n == 1:
        cnt1 += 1
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

for n in ns:
    cnt0, cnt1 = 0, 0
    fib(n)
    print(cnt0, cnt1)

 

당연하게도 그렇게 쉬운 문제는 아니었습니다.. 이렇게 풀 경우 재귀함수 호출 횟수가 너무 많아져 시간 초과가 뜨게 됩니다. n의 최대가 40인데, 40이 그렇게 큰 수가 아니라고 생각되어서 시간복잡도를 실제보다 낮게 예상하게 되는 것도 있는 것 같네요.

 

그럼 어떻게 해야 할까요? 사실 재귀가 아니라 다이나믹 프로그래밍으로 풀어야 합니다. 문제에서 준 함수가 함정이었군요..! ㅡ.ㅡ

 

한 번 차근차근 접근해 봅시다. 먼저 각각의 피보나치 수가 0과 1을 몇 번씩 출력하는지를 살펴볼까요?

 

0 : 0

1 : 1

2 : 1, 0

3 : 2(1, 0), 1

4 : 3(2(1, 0), 1), 2(1, 0)

5 : 4(3(2(1, 0), 1, 2(1, 0)), 3(2(1, 0), 1)

...

 

위에서 알 수 있듯이, n번째 피보나치 수는 먼저 n-1과 n-2로 내려온 후, 내려온 수들에 대해 각각 다시 반복해서 내려가다가, 0 또는 1까지 내려올 경우 멈추고 출력합니다. 무슨 말인지 하나하나 보도록 하죠!

 

0과 1은 각각 자기 자신을 출력합니다. 왜냐하면 이 둘은 더 이상 내려갈 곳이 없기 때문입니다.

그리고 2는 1과 0으로 내려올 수 있습니다. 그리고 이 1과 0은 더 이상 내려갈 곳이 없으니 여기서 멈추고, 출력합니다.

3을 볼까요? 2와 1로 내려옵니다. 그런데 2는 아직 더 내려갈 수가 있기 때문에 다시 1과 0으로 내려옵니다. 그래서 총 0을 1개, 1을 2개 출력하게 되죠.

이말인 즉슨 2가 0과 1이 각각 몇 개로 이루어졌는지만 알고 있다면 3은 그것에 1이 1개 있음을 더해주기만 하면 되는겁니다.

4와 5도 마찬가지입니다. 위의 메모를 참고해 보신다면 금방 이해가 가실 겁니다! 그럼 이를 어떻게 코드로 구현할까요?  바로 DP테이블에 0의 출력 횟수와 1의 출력 횟수를 튜플로 저장하는 것입니다.

dp = [(1, 0), (0, 1)]

 

DP테이블의 초기값은 위와 같이 초기화합니다. (i, j)는 0의 출력 횟수가 i, 1의 출력 횟수가 j임을 의미합니다. 즉 dp[n][0]은 n번째 피보나치 수를 구할 때 0의 출력 횟수, dp[n][1]은 n번째 피보나치 수를 구할 때 1의 출력 횟수입니다. 

 

그리고 2부터 DP테이블을 추가해나가기 시작합니다. 점화식은 아래와 같습니다!

dp[n] = (dp[n - 1][0] + dp[n - 2][0], dp[n - 1][1] + dp[n - 2][1]) 

 

정답 코드

import sys

input = sys.stdin.readline

t = int(input())
ns = [int(input()) for _ in range(t)]

dp = [(1, 0), (0, 1)]

for i in range(2, 41):
    dp.append((dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]))

for n in ns:
    print(*dp[n])

 

함정이 있어서 실버3 치고는 조금 어렵지 않았나 싶네용 ^^..