피보나치 수(c언어)

긷뚜 2020. 6. 12. 20:20

728x90

https://programmers.co.kr/learn/courses/30/lessons/12945?language=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) =

programmers.co.kr

1. n=1,2,3일때의 경우는 먼저 배열에 넣어둔다.(3이하일경우는 for문이 동작하지 않으므로)

※처음에는 재귀함수를 이용하였으나 n의 수가 커지면 시간초과가 되어 배열에 넣는 방식으로 바꿈

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int n) {
    int* answer = (int*)malloc((sizeof(int) *n )+1);
    answer[0]=0;
    answer[1]=1;
    answer[2]=1;
    int buf;
    for(int i =3;i<=n;i++){
        answer[i]=(answer[i-1]+answer[i-2])%1234567;
    }
    return answer[n];
}

728x90