[알고리즘] 백준 9711 파이썬 - 피보나치

 

9711번: 피보나치

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 

 

 

문제풀이

a=[None]*10001
a[1],a[2]=1,1
tmp=[]
#01
for i in range(1,int(input())+1):
    tmp.append(list(map(int,input().split())))
#02
for j in range(3,max(tmp)[0]+1):
    a[j]=a[j-1]+a[j-2]
#03
for i in range(len(tmp)):
    print("Case #"+str(i+1)+": "+str(a[tmp[i][0]]%tmp[i][1]))

- #01 : 입력받은 값을 tmp에 저장해준다.

- #02 : 찾아야 하는 n번째 피보나치 숫자 중 가장 큰 n까지 a[n] 값을 구해준다.

           이렇게 해주면 나머지 값들의 피보나치 숫자도 모두 구해진 상태이다.

           (입력마다 for문을 돌려서 피보나치 값을 구해주면 시간 초과가 난다.)

- #03 : 문제 형태에 맞게 출력 양식을 맞춰주면 끝이 난다.