[프로그래머스/Python] 멀리 뛰기

문제

프로그래머스 - 멀리 뛰기

해결 과정

시행착오

• 재귀로 풀면 시간초과+런타임 에러 가 난다 ㅎㅎㅎㅎㅎ

def solution(n):
    answer = 0
    if n == 1:
        answer = 1
    elif n == 2:
        answer = 2
    else:
        answer = solution(n-1) + solution(n-2)
        
    return answer%1234567

• 리스트 사용 : 2문제 런타임 에러 ㅠ -> 0,1,2일때 처리를 안해줌

def solution(n):
    answer = []
    for i in range(1,n):
        if i == 1:
            answer.append(i)
        elif i == 2:
            answer.append(i)
        else:
            answer.append(answer[i-2] + answer[i-3]) 
    result = answer[-1] + answer[-2]
    return result % 1234567

그냥 나의 풀이

def solution(n):
    answer = [0,1,2]
    if n < 3:
        return n
    for i in range(3,n):
        answer.append(answer[i-2] + answer[i-1]) 
    
    result = answer[-1] + answer[-2]
    return result % 1234567

DP 풀이

def solution(n):
	# 먼저 해줘야 함
    if n < 3:
        return n
    # dp 초기 설정값
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3,n+1):
        dp[i] = dp[i-2] + dp[i-1]
    
    return dp[n] % 1234567