목록피보나치 함수 (1)

맛동산

(파이썬)백준 알고리즘 1003번 피보나치 함수

백준 알고리즘 저지 1003번 문제 (https://www.acmicpc.net/problem/1003) 보통 피보나치의 문제와 다른점은 분할 과정에서 func(0)과 func(1)이 몇번 호출되는지를 결과로 보여줘야 한다는점. 마땅한 대책을 생각 못해서 n을 1씩 증가시키며 몇번의 0과 1이 호출되는지를 분석해보니 초기 몇가지 값 빼고는 피보나치 수열처럼 n0 = n-1 + n-2의 규칙을 띄고 있는 것을 알게됐음 이를 이용하여 함수를 만들었는데 시간초과로 통과하지 못했음. n이 40인 경우가 T번 입력되는 최악의 경우에 매번 연산을 해야했기 때문. 그래서 c0, c1이라는 배열을 만들어서 이미 계산된 n까지의 경우를 저장하도록 해서 반복연산을 줄임. c0=[1,0,1] c1=[0,1,1] def fi..
파이썬/알고리즘 2016. 12. 19. 20:58
Prev 1 Next