[프로그래머스][C++] 멀리 뛰기

멀리 뛰기

문제 링크

멀리 뛰기

풀이

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

    if (n == 1) return 1;
    if (n == 2) return 2;
    
    // n - 1
    int prev1 = 2;
    // n - 2
    int prev2 = 1;
    for (int i = 3; i <= n; ++i)
    {
        answer = (prev1 + prev2) % 1234567;
        prev2 = prev1;
        prev1 = answer;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• n을 순회하는 반복문 $O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 3.67MB)
테스트 4 〉 통과 (0.01ms, 3.68MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.14MB)
테스트 10 〉 통과 (0.01ms, 4.14MB)
테스트 11 〉 통과 (0.01ms, 3.64MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.2MB)
테스트 15 〉 통과 (0.01ms, 4.17MB)
테스트 16 〉 통과 (0.01ms, 4.14MB)