이것 또한 기본적인 재귀함수 호출 문제이다. 입력에 O(1), N일때 N-1과 N-2 를 입력으로 두개의 함수를 호출한다. O(N^2)
import sys input = sys.stdin.readline() n = int(input) def solution(n): if n==0: return 0 elif n==1: return 1 else: return solution(n-1)+solution(n-2) print(solution(n))