[프로그래머스 LV 3] 멀리 뛰기 (파이썬/python)

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

코딩테스트 연습 - 멀리 뛰기

 

처음에 완전탐색으로 풀었고 시간 초과가 났다.

더 효율적인 풀이법을 생각하다 메모이제이션을 통해 

기존에 구한 값은 더 이상 계산하지 말고 바로 반환할 수 있게

동적계획법을 사용했다.

 

나는 탑다운으로 푸는게 편해 일단 탑다운으로 풀고

바텀업으로 같은 로직을 한번 더 작성해봤다.

 

탑다운은 뒤에서부터 결과값을 갱신해주고

바텀업은 앞에서부터 결과값을 갱신해간다

 

완전탐색풀이(시간초과)

import sys
 
sys.setrecursionlimit((4000001))
 
answer = 0
 
 
def solution(n):
    global answer
 
    def jump(x):
        global answer
        if x == n:
            answer += 1
            return
        if x > n:
            return
 
        jump(x + 1)
        jump(x + 2)
 
    jump(0)
    print(answer)
    return answer

 

동적계획법 풀이(탑다운)

import sys
 
sys.setrecursionlimit((4000001))
 
 
def solution(n):
    answer = 0
    # dp[i] = n번에서 i번으로 갈 수 있는 경우의 수
    dp = [-1] * 2001
 
    def jump(x):
 
        if x == n:
            return 1
        if x > n:
            return 0
        if dp[x] != -1:
            return dp[x]
 
        dp[x] = jump(x + 1) + jump(x + 2)
        return dp[x]
 
    answer = jump(0)
 
    return answer % 1234567

 

동적계획법 풀이(바텀업)

def solution(n):
    answer = 0
 
    dp = [0] * 2001
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    answer = dp[n]
    
    return answer % 1234567