프로그래머스 LV2 - 멀리 뛰기

문제 링크

내 풀이

def solution(n):
    left = n
    right = 0
    answer = 0
    while left >= right:
        bunza = 1
        bunmo = 1
        if right == 0:
            answer += 1
        elif left == right:
            answer += 1
        else:
            for i in range(right):
                bunza *= left-i
                bunmo *= right-i
            answer += bunza // bunmo
        left -= 1
        right += 1
    return answer % 1234567

다른 풀이

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

풀이 해석

• 계단을 1,2칸만 올라갈 수 있으므로 3칸을 오를 때는 1,2칸을 오르는 경우의 수를 합해주면 되고, 점화식으로 나타내면 $f(n) = f(n-1) + f(n-2)$ 피보나치 수열을 구할 때와 같다

배울점

• 피포나치 수열의 이용