[알고리즘문제] 프로그래머스 -멀리 뛰기

 

효진이는 1칸, 2칸을 이동할 수 있습니다. 이동해야 할 n칸이 주어질 때 1칸, 2칸을 n칸에 도달할 수 있는 방법을 구하면 됩니다.

 

문제는 보자마자 앞서 이동했던 경우의 수를 사용하여 현재 구하려는 경우의 수를 구할 수 있을 것 같다는 생각을 했습니다. dp를 사용하였고 먼저 각 n마다 이동할 수 있는 경우를 구해보았습니다.

 

1 : (1)   - 1가지

2 : (1,1), (2) - 2가지

3 : (1,1,1), (1,2), (2,1) - 3가지

4 : (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2) - 5가지

5 : (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) - 8가지

 

각 칸에 대한 방법을 보면 다음과 같은 규칙이 있음을 알 수 있습니다. 피보나치 수열이네요.

 

5칸 : 4칸 방법 수 + 3칸 방법 수

4칸 : 3칸 방법 수 + 2칸 방법 수 

.....

 

먼저 dp로 풀어보았고, 재귀함수로도 한번 풀어보았습니다.

 

1. dp

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    
    long long answer = 1;
    
    long long dp[2001] = {0};
    
    dp[1] = 1;
    dp[2] = 2;
    
    for(int i=3;i<=n;i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
    }
    
    return dp[n];
}

 

2. 재귀

재귀로 풀었을 때는 7~16번 테스트케이스가 시간초과가 나왔습니다. 아무래도 1,2로 200을 표현할 수 있는 방법이 너무 많아 시간이 오래 걸린 것 같습니다.

#include <string>
#include <vector>

using namespace std;
long long count = 0;

void recur(int n,int sum){
    if(sum >= n){
        if(sum==n){
            count++;
        }
        return;
    }
    
    for(int i=1;i<=2;i++){
        recur(n,sum+i);
    }
    
}
long long solution(int n) {
    
    recur(n,0);
    return count % 1234567;
}