피보나치 수

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

프로그래머스

알게된 것

• 재귀로 하면 수가 커질 수록 시간 초과가 난다.
• memoization! 
  • 초기화
  • 반복
  • 대입
• 타입 확인 (수가 커지니까)
• 문제의 값이 커질수록 %1234567의 나머지를 넣어준 다음 더하고 또 나눠주는 방식으로 해야 통과되었다.

내코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    long long numbers[100001] = {0, };
    numbers[0] = 0;
    numbers[1] = 1;
    numbers[2] = 1;

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

    return numbers[n] % 1234567;
}

친구리뷰

• 각 numbers[i] 에서 %1234567 안하더라도 javascript 는 그냥 해주는디.

시도

• 재귀로 했으나 타임 오버.

 

References

https://school.programmers.co.kr/questions/3832

프로그래머스