풀이_멀리뛰기.md

🧚🏻‍♀️ 프로그래머스 멀리 뛰기

• Date : 2020.10.12(월)
• Time : 15분

문제

• 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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하면 됩니다.
  
  

코드 풀이

    table[0] = 1
    table[1] = 1
    for i in range(2, n+1, 1):
        table[i] = table[i-1] + table[i-2]

: 아무 칸도 안뛰는 0의 경우 -> 경우의 수 1개, 1칸만 뛰는경우 -> 경우의 수 1개, 2칸만 뛰는 경우 -> 1칸으로 뛰는 경우(2) + 2칸으로 뛰는 경우(1+1), 3칸만 뛰는 경우 -> 2칸으로 뛰는 경우(1+2, 2+1) + 3칸으로 뛰는 경우(1+1+1) … 계속 n칸으로 뛰는 경우의 수 = n-1로 뛰는 경우의 수 + n-2로 뛰는 경우의 수로 지정할 수 있기 때문에 동적 계획법을 이용했다.

동적계획법이란?

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 분할 정복법(Divide and Conquer)과 유사하다. 해결된 문제의 답을 저장해두고 그것을 재활용하여 해결된 문제를 다시 푸는 비효율을 제거한다. 공간복잡도를 늘리고 시간복잡도를 줄이는 방식이다. ex) 피보나치수