백준 1003 | DP | 피보나치 함수 [파이썬 python]

1003번: 피보나치 함수

 

코드

t = int(input()) # 테스트 케이스
for _ in range(t):
    n = int(input())

    # 0과 1의 호출 횟수(N은 40보다 작거나 같은 자연수 또는 0)
    zero = [0] * (41)
    one = [0] * (41)
    
    zero[0], one[0] = 1, 0 # f(0)
    zero[1], one[1] = 0, 1 # f(1)

    for i in range(2, n+1):
        zero[i] = zero[i-1] + zero[i-2]
        one[i] = one[i-1] + one[i-2]

    print(zero[n], one[n])

n번째 피보나치수를 구하기 위해서 0과 1이 몇 번 호출되는지 구하는 문제이다.

n = 2, 3, 4일 때 피보나치수를 구하는 과정은 다음과 같다.

• fibonacci(2) = fibo(1) + fibo(0)
• fibonacci(3) = fibo(2) + fibo(1) = (fibo(1) + fibo(0)) + fibo(1)
• fibonacci(4) = fibo(3) + fibo(2) = (fibo(2) + fobo(1)) + (fobo(1) + fibo(0)) = {(fibo(1) + fibo(0)) + fibo(1)} +(fibo(1) + fibo(0))

0과 1의 호출 횟수를 표로 나타내면 아래 그림과 같다.

0의 호출 횟수인 zero와 1의 호출 횟수인 one도 피보나치 규칙을 따르고 있는 것을 알 수 있다.

따라서 n번째 피보나치수를 구하는 함수를 조금만 변형하면 쉽게 문제를 해결할 수 있다.

 

아래는 반복문을 활용하여 피보나치 수를 구하는 코드이다.

d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 2
n = 99

# 피보나치 함수
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]

print(d[n])

이 함수에서 피보나치 수는 배열 d에 저장되었다.

우리가 구하고자 하는 것은 0과 1의 호출 횟수이므로, 피보나치 수가 아닌 호출 횟수를 저장하는 배열을 만들어주면 된다.

따라서 zero, one 이름으로 0의 호출 횟수와 1의 호출 횟수를 각각 저장할 수 있도록 하였다.

n = int(input())

# 0과 1의 호출 횟수(N은 40보다 작거나 같은 자연수 또는 0)
zero = [0] * (41)
one = [0] * (41)

zero[0], one[0] = 1, 0 # f(0)
zero[1], one[1] = 0, 1 # f(1)

for i in range(2, n+1):
    zero[i] = zero[i-1] + zero[i-2]
    one[i] = one[i-1] + one[i-2]

print(zero[n], one[n])

fibonacci(0)은 0을 한 번만 호출하므로 zero[0]=1, one [0]=0으로 바꿔주고, fibonacci(1) 역시 1을 한 번만 호출하므로 zero[1]=0, one[1]=1로 바꿔준다.

두 번째 이후의 피보나치 수를 구하기 위해 호출하는 0의 횟수는 zero[i-1]+zero[i-2]로, 1의 횟수는 one[i-1]+one[i-2]로 구해준다.

 

위 코드를 테스트 케이스의 수만큼 반복해 주면 된다.