프로그래머스 LV.2 멀리 뛰기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

 

해당 문제를 해결하기 위해서는

일단 효진이의 멀리 뛰기 경우의 수를 구하는 것이 먼저다.

 

N번째 경우의 수는 N-1번째 경우의 수 + N-2번째 경우의 수와 같다.

 

이는 마치 피보나치 수열과 유사하다.

피보나치 수열은 n = n-1 + n-2의 관계성을 띈다.

다만 피보나치 수열과 다른점은 피보나치는 

첫째 및 둘째 항이 1인데 그것만 제외하면 피보나치 수열과 동일하다.

 

이렇게 나온 값 % 1234567 = answer이 된다.

 

시간초과 난 코드

#include <string>
#include <vector>

using namespace std;

long long longjumpAnswer(long long n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else if (n == 2) return 2;
    else {
        return longjumpAnswer(n - 1) + longjumpAnswer(n - 2);
    }
}

long long solution(int n) {
    long long answer = longjumpAnswer(n) % 1234567;

    return answer;
}

 

 

시간을 줄이기 위해 쓴 코드 -

오답처리됨 아마 숫자가 너무 커서 그런갑다 싶었다.

long long solution(int n) {
    int answer = 0;
    if (n == 0) return 0;

    vector<long long> longjumpArr;
    longjumpArr.push_back(1);
    longjumpArr.push_back(2);

    for (int i = 2; i < n; i++) {
        longjumpArr.push_back (longjumpArr[i - 1] + longjumpArr[i - 2]);
    }

    answer = longjumpArr[n-1] % 1234567;

    return answer;
}

 

 

정답 코드

long long solution(int n) {
    int answer = 0;

    if (n == 0) return 0;

    vector<long long> longjumpArr;
    longjumpArr.push_back(1);
    longjumpArr.push_back(2);

    for (int i = 2; i < n; i++) {
        longjumpArr.push_back((longjumpArr[i - 1] + longjumpArr[i - 2]) % 1234567);
    }

    answer = longjumpArr[n - 1];

    return answer;
}