[Python Silver III 1003] 파보나치 함수

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

1003번: 피보나치 함수

시간 제한	메모리 제한
0.25초	128MB

 

문제

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

def fibonacci(n):
    if (n == 0):
        print("0")
        return 0
    elif (n == 1):
        print("1")
        return 1
    else:
        return fibonacci(int(n-1)) + fibonacci(int(n-2))

• fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

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

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

 

입력

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

 

출력

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

 

알고리즘 분류

• 다이나믹 프로그래밍

 

---

 📖 Code

Count = int(input())
for i in range(Count):
    N1,N2,N3 = 1,1,0
    NUM = int(input())
    if NUM == 0:
        print(1, 0)
    elif NUM == 1:
        print(0, 1)
    elif NUM == 2:
        print(1, 1)
    else:
        for i in range(2, NUM):
            N3 = N2 + N1
            N1 = N2
            N2 = N3
            if NUM-1 == i:
                print(N1, N2)

 ✅ Comment

시간제한이 0.25초라 하나하나 계산하게 된다면 시간초과가 될 거라고 생각하고 접근했다.

또 문제에서 주어진 함수로.

숫자를 하나하나 계산해보며 규칙을 찾았는데.

 

	0 개수	1 개수	0+1 개수
fabonacci( 1 )	1	0	1
fabonacci( 2 )	1	1	2
fabonacci( 3 )	1	2	3
fabonacci( 4 )	2	3	5
fabonacci( 5 )	3	5	8
fabonacci( 6 )	5	8	13
fabonacci( 7 )	8	13	21

 

이런 식으로

0과 1의 숫자의 합은. 기준이 되는 숫자를 N이라고 했을 때.

N-1과 N-2의 0+1의 숫자의 합을 더한 수가 N의 0+1의 합이 됩니다.

또한.

N-1 의 0+1  값은. N의 1의 개수가 되고.

N-2 의 0+1 값은. N의 0의 개수가 되는 점도 확인할 수 있습니다.



이 규칙을 이용해서 코드를 작성하면 시간제한에 걸리지 않게 코드를 작성할 수 있습니다.