[프로그래머스/C++] 피보나치 수

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

피보나치 수

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한사항

•  n은 2 이상 100,000 이하인 자연수입니다.

 

풀이

입출력 예시

 

풀이

피보나치 수열은 위의 설명과 같이, F(n) = F(n-1) + F(n-2) 가 적용되는 수이다. 간단하다, F(n-2)를 저장하는 변수를 선언해주고, answer은 f(n-1)이었을 상태로 지정해준다. 이후, 저 규칙에 맞게 연산을 시켜주자.

int solution(int n) {
    int answer = 1; // == f(n-1)
    int before = 0; // == f(n-2)
    int tmp;

    for (int i = 2; i <= n; i++) {
        tmp = answer;
        answer += before; // == f(n)
        before = tmp;
    }
    return answer % 1234567;
}

결과?

간단할리가 없었다. 무엇이 문제일까? 제한 사항을 다시 읽어보자. n은 2이상 10만 이하의 자연수다. 아, 설마 수가 너무 커서 오버플로우가 되어버린 것일까? 3500을 넣고 테스트를 돌려봤더니, 정말로 오버플로우가 일어났다. ;; 혹시 자료형으로 unsigned long long을 쓰면 되지 않을까 싶었지만 마찬가지로 오버플로우가 일어났다...

 

문제에서 1234567로 나누라는 것이 이것 때문이라고 생각했다. 그런데 이걸 어떻게 이용할까? 나머지 연산에 대해 검색을 하던 중 나는 매우 유용한 공식을 하나 알게됐다.

 

(A + B) % C = ((A % C) + (B % C)) % C

 

이걸 피보나치 수에도 적용시켜보자.

F(n) % 1234567 = (F(n-1) + F(n-2)) % 1234567 = ( F(n-1) % 1234567 + F(n-2) % 1234567 )

위의 코드를 수정해보자!

int solution(int n) {
    int answer = 1; // == f(n-1) % 1234567
    int before = 0; // == f(n-2) % 1234567
    int tmp;

    for (int i = 2; i <= n; i++) {
        tmp = answer;
        answer = (answer % 1234567 + before % 1234567) % 1234567; // == f(n) % 1234567
        before = tmp;
    }
    return answer;
}

결과