[63일차][Lv2][프로그래머스][12914]멀리 뛰기

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

제한 사항

n은 1 이상, 2000 이하인 정수입니다.

   

입출력

n	result
4	5
3	3

 

코드 및 설명

def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        n_arr = [0] * n
        n_arr[0] = 1
        n_arr[1] = 2
        
        for idx in range(2, n):            
            n_arr[idx] = n_arr[idx-1] + n_arr[idx-2]
                                             
    return n_arr[n-1] % 1234567

이 문제는 피보나칠 수열로 푸는 문제이다. 먼저 n이 1일 때와 2일 때는 return을 직접 해줬고, 다음 수 부터는 n_arr의 0번쨰와 1번째에 1, 2를 세팅하고, n = (n - 1) + (n - 2)를 해준다. n == 3이면 n_arr = [0,0,0]이 세팅되고, 0번째에 1, 1번째에 2를 세팅하면 [1,2,0]이 된다. 그 이후 n_arr[1]와 n_arr[0]의 값을 더해주면 3이 된다. 

 

[1,2,3,0]

만약 n이 4라면 위에서 n == 3일때 구한 값 n_arr[2]와 n_arr[1]을 더하면 5가 된다. 

 

이것 또한 처음 풀 때 재귀함수로 풀어보려고 했으나, 시간초과 및 이해도가 떨어져 삽질을 계속 하던 중 , 피보나치 수열이 언뜻 기억나서 겨우겨우 풀었다. 생각보다 하나하나 푸는게 너무 쉽지않은 것 같다...

 

피보나치 수열 나무 위키 : https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4