프로그래머스 - 멀리 뛰기(C++)

한칸 아니면 두칸 이동할 수 있다. 처음에는 여러가지 방법으로 한 곳으로 간다고 생각하고 백준 숨바꼭질 2를 떠올려 BFS로 구현했으나

#include <string>
#include <vector>
#include <queue>
using namespace std;

bool visited[2001] = {false,};
queue<int> Q;
long long cnt = 0;
void BFS(int n){
    Q.push(0);
    while(!Q.empty()){
        int X = Q.front();
        Q.pop();
        
        visited[X] = true;
        
        if(X == n){
            cnt++;
        }
        
        if(X + 1 <= n && visited[X + 1] == false){
            Q.push(X + 1);
        }
        if(X + 2 <= n && visited[X + 2] == false){
            Q.push(X + 2);
        }
    }
}

long long solution(int n) {
    long long answer = 0;
    BFS(n);
    answer = cnt % 1234567;
    return answer;
}

 

처참한 시간복잡도를 자랑했다. 중복처리만 잘 하면 생각했으나 생각해보니까 이건 최소 뛰기로 가는것도 아니고 "모든" 값을 찾아내야한다. 그러니까 중복처리를 하면 안된다. 즉 BFS의 시간복잡도로는 1+...+1 부터 1+...+2 .... 2+...+2 까지 뭐그냥 엄청나게 많다. 그래서 어떻게 풀까 하다가 DP를 생각했다.

 

쭉 써보면

DP[1] = 1

DP[2] = 2

DP[3] = 3

DP[4] = 5

 

조금만 보면 DP[i] = DP[i -1] + DP[i -2] 임을 알 수 있다. 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

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

 근데 아쉬운 것은 난 처음에

 for(int i = 3; i <= n; i++){
        DP[i] = (DP[i - 2] + DP[i - 1]);
    }
    answer = DP[n]  % 1234567;
    return answer; 

 

이렇게 했는데 37점 나왔다. 결국 구글링을 했는데 점화식이 틀린건 아니고 겨우 저거였다. 아무래도 long long 으로도 담기 힘든 큰 수인 것 같다. 그리고 결국은 나머지를 출력하는 것이니 미리 해놓고 더해도 상관이 없다. 1 * 123 + 2 * 123 = (1 + 2) * 123 과 같은 분배법칙을 생각하면 쉽다.