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

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

 

코딩테스트 연습 - 멀리 뛰기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

문제 설명

 

문제설명 1

 

문제설명 2

문제에서 주어진 것

 

• 뛸 수 있는 거리는 1 or 2칸
• 문제에서는 n칸이  주어짐
• 이때 1과 순서가 달라지는 것도 수 체크에 들어감

 

이때 본인이 n의 거리를 뛸 경우 경우의 수 % 1234567를 구하기

 

문제 풀이

 

먼저 적은 수의 경우 뛸 수 있는 경우의 수를 계산해 보았다.

 

뛰는 거리	1	2	3	4	5	6
경우의 수	1	2	3	5	8	13

 

해당 표는 1,2로 뛸 수 있는 방법의 개수를 파악하기 위해 경우의 수를 도출한 것. 근데 익숙한 숫자의 배열이 보인다.

바로 피보나치의 수 0,1,1,2,3,5,8,13.... 의 피보나치 수이다. 다만 이런 문제의 경우 처음부터 피보나치라는 것을 알 수는 없고 구하고 나니 피보나치와 같은 경우의 수가 나온 것이다. 그럼 점화식을 살펴보자.

 

dp [i] = dp [i-1] + dp [i-2]  (이때 i는 3부터)

 

해당 점화식을 통해 문제를 풀이해나가면 된다. 이때 문제 풀이의 방법은 dp - 다이내믹 프로그래밍으로 접근한다.

 

문제 풀이

 

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