꾸준한 번식 – 피보나치 수열, 동적 프로그래밍 [코딩테스트 Python]

시나리오

언휴는 이상한 꿈을 꾸었죠. 꿈 속에 요정이 나타나 다음과 같은 말을 했어요.

“얘는 하루가 지나면 임신을 할 수 있어. 그리고 다음 날 부터 매일 한 마리씩 출산을 하지.

출산한 새끼들도 마찬가지야.”

꿈에서 깨었을 때 귀여운 생명체가 방에 있는 것을 알 수 있었죠.

요정의 말이 사실이라면 60일에는 몇 마리로 번식할 지 계산하고는 놀랐다고 하네요.(오늘을 1일이라고 가정)

언휴는 왜 놀랐는지 날짜 별로 개체 수를 확인하는 코드를 작성해 보세요.

(*단 결과는 1초 이내에 나와야 합니다.)

문제

난이도: 2 (easy) [1:very easy, 2:easy, 3:middle, 4: difficult, 5: very difficult]

입력: 60

출력:1548008755920

설명:

첫 날은 1,

두 번째 날에는 임신 능력 생김. 개체 수는 여전히 1

세 번째 날은 출산하여 1+1 =2. 출산한 자식은 임신하지 못함

네 번째 날도 출산하여 2+1=3. 세 번째 날에 출산한 자식은 임신 능력 생김

다섯 번째 날도 출산하여 2+3=5. 네 번째 날에 출산한 자식도 임신 능력 생김

…

개체 수는 1 1 2 3 5 8 13 과 같은 수열을 통해 알 수 있다.(Fibonacci 수열)

코드

def Breed(n):

print(Breed(60))

솔루션

answers=[0,1,1]
def Breed(n):
    if n<=0:
        return 0
    if n<len(answers):
        return answers[n]
    answers.append(Breed(n-1)+Breed(n-2))
    return answers[n]
print(Breed(60))

주의할 점

다음처럼 구현하면 수행 시간이 너무 오래 걸림

def Breed(n):
    if n<=0:
        return 0
    if (n==1) or (n==2):
        return 1
    return Breed(n-1)+Breed(n-2)
print(Breed(60))