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

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

문제

나의 풀이

총 세 가지 풀이.

첫번째, 경우의 수 구하는 과정을 공식화한 코드.
두 칸 오르는 횟수를 A, 한 칸 오르는 횟수를 B라고 했을 때
A의 최댓값부터 0이 될 때까지 1씩 줄여가며 A와 B의 가능한 경우의 수를 모두 구했다.
그 후 순서를 지정하는 과정을 팩토리얼을 통해 나타냈다.

def fact(x):
    if x <= 1:
        return 1
    return x * fact(x-1)

def solution(n):
    answer = 0
    for cnt2 in range(n // 2, -1, -1):
        cnt1 = n - cnt2 * 2
        if cnt1 == 0 or cnt2 == 0:
            answer += 1
        else:
            answer += fact(cnt1 + cnt2) // (fact(cnt1) * fact(cnt2))
    return answer % 1234567

하지만 몇 테스트 케이스에서 시간 초과로 오류가 발생했다.

두번째는 피보나치 수열.
위의 함수를 적용해 n이 1일 때부터 차근차근 return 되는 값을 나열했더니 피보나치 수열의 규칙을 따랐다.

def fibo(x):
    if x <= 3:
        return x
    return fibo(x-1) + fibo(x-2)

def solution(n):
    return fibo(n) % 1234567

하지만 이 역시 불필요한 재귀함수가 많이 생성되어 시간 초과로 오류가 발생했다.

마지막, 통과 함수는 아래와 같다.
다이나믹 프로그래밍을 활용하여 불필요한 재귀함수를 부르지 않고 메모리를 활용하는 것.

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

다른 풀이

얻어가기

피보나치 수열은 다이나믹 프로그래밍 활용 예시 중 대표적이다.