공부 자료/알고리즘
(Python/파이썬) 백준 1003번 - 피보나치 함수
뚜루뚜루세니
2021. 8. 3. 10:57
728x90
문제출처: https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
zero = [1,0,1]
one = [0,1,1]
for i in range(3,41):
zero.append(zero[i-1]+zero[i-2])
one.append(one[i-1]+one[i-2])
test = int(input())
for i in range(test):
n = int(input())
print(zero[n], one[n])
|
cs |
2. 해결과정
피보나치 함수에서 0과 1이 리턴되는 횟수를 구하는 문제이다.
fibonacci(n)을 호출한다면, 실행되는 fibonacci(0)과 fibonacci(1)은 'fibonacci(n-1)의 0과 1 호출 횟수' + 'fibonacci(n-2)의 0과 1 호출 횟수'와 동일하다.
따라서 같은 방식으로 호출 횟수를 구해주면 된다.
zero와 one 배열에 미리 n이 0~2까지일 경우에 호출되는 횟수를 넣어주고, 그 후부터는 계산을 해서 넣어주게 설정하였다.
3. 느낀점
간단하게 dp를 이용해서 풀 수 있었던 문제
728x90