[프로그래머스/C++ 문제 풀이] Lv. 2 - 멀리 뛰기

문제 설명

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

입출력 예

 

입출력 예 #1
위에서 설명한 내용과 같습니다.

 

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

---

문제 풀이

저는 이번 문제를 처음 보고 모든 방법의 수를 구하는 문제이기에 모든 경우의 수를 전부 체크하면 되겠다는 생각으로 완전탐색으로 접근을 시도했습니다.

 

하지만 최대 크기가 2000인 N을 1칸 or 2칸씩 움직이는 과정에서 시간초과가 발생하여 오답을 받았으며, 수학적으로 식을 세울 수 있는지 체크해보기 시작했습니다.

 

손으로 간단히 1 ~ 6까지 경우의 수를 세어보니 피보나치 수와 유사한 결과를 얻어 피보나치 수열을 DP를 사용해 구현하게 되었으며, 문제를 해결할 수 있었습니다.

 

아직은 문제와 알고리즘만을 가지고 시간복잡도를 체크하는 것이 미숙한 것 같습니다.  

정답 코드

풀이 시간 : 15m 39s

#include <string>
#include <vector>

using namespace std;

long long cnt;

int DP[2002];

int Fibo(int n)
{
    if (n <= 3) return n;
    
    if (DP[n] == 0) 
    {
        DP[n] = Fibo(n - 2) + Fibo(n - 1) ;
        return DP[n] % 1234567;
    }
    else
    {
        return DP[n];   
    } 
}

long long solution(int n) {

    // n = 1 : 1
    // n = 2 : 2
    // n = 3 : 3
    // n = 4 : 5
    // n = 5 : 8
    // n = 6 : 13
    // -> 피보나치 수열과 비슷
    
    return Fibo(n);
}