[프로그래머스][파이썬] 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

def solution(n):
    answer = 0
    str1 = [1,1] #피보나치 수열 리스트
    str2 = [1,2,3] #경우의 수 리스트
    
    if n >= 4:
        for i in range(4, n+1):
            str1.append(str1[-1]+str1[-2]) #n까지 피보나치 수열 추가
            str2.append(str2[-1]+str1[-1]) #n까지 경우의 수 추가
    
    return str2[n-1] % 1234567

 

• 가장 먼저 경우의 수를 계산하는 규칙이 있는지 확인한 결과, 피보나치 수열로 증가한다는 점을 발견했다.
• 그래서 피보나치 수열을 저장하는 리스트 str1, 경우의 수를 저장하는 리스트 str2를 각각 만들었고 n=1, 2, 3일 때의 기본값을 줬다.
• 4이상의 n에 대해서는 1씩 증가시키며 피보나치 수열을 만들고, str2에 피보나치 수를 더해가는 식으로 계산했다.
• 다른 사람의 풀이를 확인한 결과, dp[n] = dp[n-1] + dp[n-2] 점화식을 활용해 재귀함수로 작성한 사람이 많았다.