피보나치 함수
https://www.acmicpc.net/problem/1003 (opens in a new tab)
내 풀이
첫 번째 풀이
시간 초과 오류가 발생한다. 아래 코드의 원리는 딱히 없다.
예를 들어, n = 3일 때, 피보나치 수열을 실행하면서 fibo(0)과 fibo(1)을 실행할 때마다 0, 1, 0 또는 1, 0, 1을 반환하고 fibo(n-1)과 fibo(n-2)를 실행할 때마다 fibo(n-1)의 cnt_0과 fibo(n-2)의 cnt_0을 더하고 fibo(n-1)의 cnt_1과 fibo(n-2)의 cnt_1을 더한다.
이런식으로 완전 탐색을 하는 함수이다.
test_case_count = int(input())
def fibo(n, cnt_0, cnt_1) :
if n == 0 :
return 0, 1, 0
if n == 1 :
return 1, 0, 1
fibo1_data = fibo(n - 1, 0, 0)
fibo2_data = fibo(n - 2, 0, 0)
val = fibo1_data[0] + fibo2_data[0]
cnt_0 = fibo1_data[1] + fibo2_data[1]
cnt_1 = fibo1_data[2] + fibo2_data[2]
return [val, cnt_0, cnt_1]
for _ in range(test_case_count) :
n = int(input())
v,cnt_0,cnt_1 = fibo(n, 0, 0)
print(f"{cnt_0} {cnt_1}")내 풀이 2
https://bio-info.tistory.com/122 (opens in a new tab) 👈 이 블로그에서 아이디어를 얻었는데 0이 호출된 횟수와 1이 호출된 횟수 역시 피보나치 수열을 이룬다는 아이디어에 착안해서 dp로 풀었다.
test_case_count = int(input())
cnt0_map = {}
cnt1_map = {}
cnt0_map[0] = 1
cnt0_map[1] = 0
cnt1_map[0] = 0
cnt1_map[1] = 1
def fibo(n) :
cnt0 = 0
cnt1 = 0
if n not in cnt0_map :
cnt0 = fibo(n - 1)[0] + fibo(n - 2)[0]
cnt0_map[n] = cnt0
else :
cnt0 = cnt0_map[n]
if n not in cnt1_map :
cnt1 = fibo(n - 1)[1] + fibo(n - 2)[1]
cnt1_map[n] = cnt1
else :
cnt1 = cnt1_map[n]
return [cnt0, cnt1]
for _ in range(test_case_count) :
n = int(input())
cnt0, cnt1 = fibo(n)
print(f"{cnt0} {cnt1}")