# 프로그래머스 : 멀리 뛰기 (Level 3)

[문제]

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

[풀이]

이 문제 처음 보고 너무 막막했는데, 차근차근 접근해보니까 굉장히 놀랍게도 '피보나치'와 동일하였다.

• 1칸 : 1가지 방법
• 2칸 : 2가지 방법
• (1,1) , (2,0)
• 3칸 : 3가지 방법
• (1,1,1) , (1,2) , (2,1)
• 4칸 : 5가지 방법
• (1,1,1,1) , (1,2,1) , (1,1,2) , (2,1,1), (2,2)
• 5칸 : 8가지 방법
• (1,1,1,1,1) , (1,1,1,2) , (1,1,2,1) , (1,2,1,1) , (2,1,1,1) , (1,2,2) , (2,1,2) , (2,2,1)

이런식으로 진행하면 결국 식은 다음과 같다.

멀리뛰기(n) = 멀리뛰기(n-2) + 멀리뛰기(n-1);

이를 코드로 표현하면,

int jumpCase(int n)

{

    int answer = 0;

    if(n == 1) return 1;

    else if(n == 2) return 2;

    

    answer = jumpCase(n-2) + jumpCase(n-1);

    return answer;

}

처음에 문제를 보고 상당히 어렵게 접근하려고 했는데,

몇가지 테스트 케이스를 통해 공식을 유도하고 나니 피보나치라는 간단한 방식이었다.