백준 1003번 피보나치 함수 - Python

문제

다음 소스는 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

3
0
1
3

예제 출력 1

1 0
0 1
1 2

예제 입력 2

2
6
22

예제 출력 2

5 8
10946 17711

 

위 문제를 해결하는데 있어서 처음에는 문제에서 설명하는 재귀용법을 이용하되 zero와 one에 읽혀질때마다 count를 올리는 방식으로 해결하고자 접근했습니다.  하지만 시간초과가 발생했습니다. 

def fibonacci(num):
    global zero
    global one

    if num == 0:
        zero += 1
        return 0
    elif num == 1:
        one += 1
        return 1
    else:
        return fibonacci(num-1) + fibonacci(num-2)

zero = 0
one = 0
N = int(input())
problem = []
ans = []
for i in range(N):
    problem.append(int(input()))

for i in range(N):
    fibonacci(problem[i])
    print(zero, one)
    zero = 0
    one = 0

 

재귀용법을 활용한 문제는 DP로 풀 수 있는 경우들이 있는데 피보나치 문제가 대표적입니다. 피보나치 수는 n에 대한 값을 구하기 위해서 n-1과 n-2의 값을 더해줍니다. 즉 n이 가장 아래로 내려가게 되면 0과 1을 이용하게 됩니다. 배열로 구성해서 0부터 계산한다고 한다면 차례대로 수는 그 이전의 2개의 값을 더해서 해당하는 값을 계산해줍니다. 

입력사이즈가 40밖에 안 되기 때문에 위 방식으로 풀어보려고 했으나.. 테스트 케이스의 갯수가 적히지 않은 것으로 보아 굉장히 큰 사이즈도 테스트 케이스에 들어가 있는 거 같습니다. 또한, 시간이 0.25초 인 것도 무시할 수 없고요...

그래서 DP 방식으로 해결했습니다. 

# DP를 위한 사전 계산
fiboZeroOne = [[1, 0], [0, 1]]  # 0과 1에 대하여 사전에 초기화
problem = []
for i in range(2, 41):
    zero = fiboZeroOne[i - 2][0] + fiboZeroOne[i - 1][0]
    one = fiboZeroOne[i - 2][1] + fiboZeroOne[i - 1][1]
    fiboZeroOne.append([zero, one])

# 입력
T = int(input())
for _ in range(T):
    problem.append(int(input()))

# 출력
for j in range(T):
    x = fiboZeroOne[problem[j]]
    print(x[0], x[1])

 미리 0과 1에 대한 값은 정리를 해줍니다. 문제에서 요구하는 결과값은 각 입력되는 값에 대하여 0과 1이 얼만큼 사용되었는지를 카운트 한 값을 출력하라는 것 입니다. 

예를 들어서 내가 만약 N번째 수에 3라는 값을 입력했다고 가정해보겠습니다. fibonacci 수를 생각해본다면 수열 순서(0부터 시작한다고하면)가 0 1 1 2 3 ...가 됩니다.  3번째 수는 2 입니다. 2라는 값은 앞에 있는 1과 1을 참조하게 됩니다. 앞에 있는 1은 이전 값이 없기 때문에 [0,1]의 값이지만 2번째 1은 0과 1을 더해서 만든 값이므로 [1,1]의 값이 들어있습니다(0,1을 참조했었다는 것입니다)  그래서 2의 값은 [1,2]가 됩니다. 

2번째 1의 값은 앞에 있는 0과 1의 값을 더해서 만들어지는 것을 이용한 맨 밑바닥에서부터 원하는 수가 있는 곳 까지 가는 것이므로 Bottom-UP 방식으로 문제를 해결한 것입니다. 

DP 문제를 해결할 때에는 반복되는 패턴이 존재하는 것을 통해서 문제 해결방법을 유추할 수 있다는 것이 특징입니다. 

위 문제는 Python으로도 좀 더 빠른 pypy로도 해결이 됩니다!