[백준/Python] 피보나치 함수

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

1003번: 피보나치 함수

이 문제는 동적계획법 문제였다. 동적 계획법 문제는 "규칙성"을 찾는 것이 중요하다. "규칙성"이 문제를 해결하는 핵심이 된다. 이 문제에서는 규칙성에 대해 친절히 설명해주어서 규칙성을 찾을 필요는 없었다. 피보나치의 규칙성은 f(n) = f(n-1) + f(n-2) 이다.

N = int(input())
zero = [1, 0, 1] # 0의 개수 리스트
one = [0, 1, 1] # 1의 개수 리스트

for _ in range(N):
	n = int(input()) # n번째를 의미하는 변수
	length = len(zero)

	if n >= length: # 0과 1의 개수를 계산해야 한다면(리스트에 계산한 정보가 없음)
		for i in range(length, n+1): # 0과 1의 개수를 계산한다
			zero.append(zero[i-1] + zero[i-2])
			one.append(one[i-1] + one[i-2])
	print(zero[n], one[n])

1. zero는 각 n번째의 0의 개수를 저장하는 리스트이고, one은 각 n번째의 1의 개수를 저장하는 리스트이다.

2. 동적계획법으로 n번째의 0과 1의 개수를 출력한다.

    2-1. 리스트에 계산한 정보가 없다면 0과 1의 개수를 계산한다.