코드업(codeup) 3709 : 블럭 채우기 1 C언어

▶문제 : 블럭 채우기 1 (codeup.kr)

블럭 채우기 1

 

▶코드 작성

#include <stdio.h>

int memo[10001];//메모이제이션

int func(int i)//피보나치 수
{
    if (i == 1) return 1;
    else if (i == 2) return 2;
    else if (memo[i] == 0) return memo[i] = (func(i - 1) + func(i - 2)) % 100000007;
    //메모에 없으면 재귀함수로 값을 구해서 적음
    else return memo[i];
    //메모가 있으면 메모를 반환함
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", func(n));

    return 0;
}

 

▶해석

n=1 일 때 1 , n=2 일 때 2 , n=3 일 때 3 , n=4일 때 5 , n=5 일 때 8...

블럭을 계산해보면 1 2 3 5 8...로 피보나치수열로 이루어진 것을 볼 수 있다.

재귀 함수로 피보나치수열을 구하는데 메모이제이션을 이용하여 빠르게 계산하도록 하였다.