백준 1003(피보나치 함수) 파이썬(Python) 해결

 

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

문제

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

 

 

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, 1로 시작하면서 다음 수부터는 앞의 두 수의 합의 결과인 수열입니다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, ...

 

피보나치의 수를 계산하는 함수를 피보나치 함수라고 하겠습니다.

재귀 함수를 통해서 구현하는 문제로 볼 수 있으며 python3 코드로 함수를 정의하면 다음과 같습니다.

 

 

피보나치 함수를 사용하여 피보나치 수열을 리스트로 표현하는 코드를 만들어 보았습니다.

 

 

 

출력 결과

 

---

문제 풀이

문제에서는 피보나치 함수를 그대로 사용하지 않았습니다.

 

 

0과 1의 출현 개수를 물어보았기 때문에 약간의 변형이 필요합니다.

처음에는 0과 1이 되었을 때 카운트하는 변수에 출현 개수를 저장했습니다.

결과는 잘 나왔지만 백준에서는 "시간 초과"로 문제 해결을 하지 못했습니다.

 

 

좀 더 빠르게 처리할 수 있는 방법을 요구했던 것입니다.

빠르게 해결하기 위해서는 수를 구하기 위해 재귀 함수를 사용하면 안 됩니다.

최종 처리까지 계속 함수를 호출하는 구조이기 때문입니다.

 

 

따라서 0과 1의 출현 개수의 규칙을 찾아내기 위해 다른 테스트 케이스를 통해 알아보았습니다.

 

 

0과 1 출현 규칙

 

 

피보나치 수의 생성 규칙과 동일한 방식으로 0과 1이 출현하는 것을 알았습니다.

 

 

즉, 0과 1로 시작하며 그다음부터는 이전 두 수의 0과 1의 출현 개수를 더한 값과 같았습니다.

 

 

알아낸 규칙을 통해서 재귀 함수를 사용하지 않고 구현한 코드는 아래와 같습니다.

 

 

 

cnt0 = [1, 0] cnt1 = [0, 1]     -> 0과 1의 출현 개수를 저장하는 리스트입니다.         0과 1일 때의 출현 개수를 먼저 저장합니다.     if test_case == 0:         print("1 0")      elif test_case == 1:         print("0 1")     else:         for j in range(2, test_case+1):                 cnt0.append(cnt0[j-1] + cnt0[j-2])                 cnt1.append(cnt1[j-1] + cnt1[j-2])         print(f"{cnt0.pop()} {cnt1.pop()}"         cnt0 = [1, 0]         cnt1 = [0, 1]     -> 입력값이 0과 1일 때에는 문제에서 요구하는 출력 형태에 맞게 출력합니다.         입력값이 2 이상일 때에는 for문을 통해 2 이상의 값에 대한 0과 1의 출현 개수를 계산합니다.         계산이 끝나면 리스트의 가장 마지막에 있는 값을 pop하여 출력 결과에 적용합니다.         다음 입력에 대한 계산을 위해 리스트를 처음 상태로 초기화 합니다.

 

 

 

- 끝 -