프로그래머스 - 피보나치 수(c++)

문제 설명

피보나치 수는 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은 1이상, 100000이하인 자연수입니다.

 

입출력 예

 

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

풀이

피보나치는 재귀 방법으로 풀게 되면 입력값이 큰 경우 시간이 많이 소요된다.

피보나치 수를 구할 때 단순히 생각하면 크게 3가지의 저장값이 필요하다.

 

1번째 : 전전 값

2번째 : 전 값

3번째 : 앞 두개의 원소를 더한 값

 

이것을 배열로 나타낸 것이 f 배열이다.

원소의 2번째, 3번째 값을 하나씩 앞으로 당겨 1번째, 2번째 위치로 옮기고 3번째 위치에는 1번째와 2번째 값을 더해 저장한다.

이것을 입력값 n의 크기만큼 반복한다.

int fibo(int n){
    int f[3] = {0,0,1};
    
    for(int i=1; i<n; i++){
        f[0] = f[1];
        f[1] = f[2];
        f[2] = (f[0] + f[1]) % 1234567;
    }
    
    return f[2];
}

int solution(int n) {
    return fibo(n);
}