개발/algorithm
[백준 1003번] 피보나치 함수 - python
zzi_on2
2022. 2. 13. 20:03
문제 링크
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
풀이
- dp 문제
- N일 때 0이 등장하는 개수를 저장하는 배열 : zero
- N일 때 1이 등장하는 개수를 저장하는 배열 : one
- 점화식
zero[i] = zero[i-1] + zero[i-2]
one[i] = one[i-1] + one[i-2]
1. N의 범위가 0부터 40이므로 각 배열을 [0] * 41 로 초기화
2. 3부터 41까지 one과 zero 값 구하기
3. 주어진 숫자에 해당하는 값 출력
n = int(input())
zero = [0] * 41
zero[0] = 1
zero[1] = 0
zero[2] = 1
one = [0] * 41
one[0] = 0
one[1] = 1
one[2] = 1
for i in range(3, 41):
zero[i] = zero[i-1] + zero[i-2]
one[i] = one[i-1] + one[i-2]
for _ in range(n):
num = int(input())
print(zero[num], end =" ")
print(one[num])