[python] 백준 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1 복사

3
0
1
3

예제 출력 1 복사

1 0
0 1
1 2

예제 입력 2 복사

2
6
22

예제 출력 2 복사

5 8
10946 17711

 

풀이

위의 함수를 실행 시켰을때 1 출력 개수와 0 출력 개수 구하기이므로

처음에는 단순하게 1출력되는 개수와 0 출력되는 개수를 그대로 세면 되는 간단한 문제아닌가? 라고 뇌빼고 잠깐 생각했다가

그렇게 하면 당연히 시간초과가 날것같았다

 

f(3) = f(2) + f(1) + f(0)

f(4) = f(3) + f(2) + f(1) + f(0)

..

이런식으로 갔을때, f(4)를 알기 위해 f(3)을 다시 실행시키는것 보다,

이전의 내용들을 저장하고 있다면, 훨씬 빠르게 f(n)에 해당하는 값을 구할 수 있을 것 같았다.

 

규칙 

f(0) = [0,1]

f(1) = [1,0]

f(2) = [1,1]

f(3) = [2,1]

..

f(n) = [이전 두개의 0번째 값의 합, 이전 두개의 1번째 값의 합]

 

f(3)을 실행한다면,  f(2) + f(1) + f(0)가 리턴 될거기 때문에, 해당 함수를 돌렸을때 출력되는 0의 개수와 1의 개수만을 저장하여 더해주면 된다. (함수를 직접 돌릴 필요 X)

 

그래서 우선 이차원 리스트를 만든 후,

L = [[0,0] for _ in range(41)]

L[0]과 L[1]은 f(0)과 f(1)을 실행했을때의 0과 1의 개수를 각각 저장해주었다.

L = [[0,0] for _ in range(41)]
L[0] = [1,0]
L[1] = [0,1]

 

그리고 이어서 규칙대로 앞의 두 리스트 값들을 더하여 채워나가면 된다.

for j in range(2,a+1):
	L[j][0] = L[j-2][0] + L[j-1][0]
    L[j][1] = L[j-2][1] + L[j-1][1]

 

 

정답 코드

import sys
input = sys.stdin.readline
T = int(input())
L = [[0,0] for _ in range(41)]

L[0] = [1,0]
L[1] = [0,1]
#print(L)
for i in range(T):
    a = int(input())
    for j in range(2,a+1):
        L[j][0] = L[j-2][0] + L[j-1][0]
        L[j][1] = L[j-2][1] + L[j-1][1]
    print(*L[a])