[C] 백준 | 13301번 코드 - 타일 장식물

>문제

www.acmicpc.net/problem/13301

13301번: 타일 장식물

> 핵심

피보나치 수열

DP

long long형

>풀이과정

피보나치 수열을 이용해서 풀 수 있다.

 

n = 5일때 길이는

(5 * 2) + ((3+5) * 2)

다시말해 dp[n] = (dp[n] * 2) + ((dp[n-1] + dp[n]) * 2) 

 

(배열 인덱스가 0부터 시작하므로 아래 코드에는 n-1, n-2로 이용함.)

 

근데 이게 초등부 문제라는데 경악을 금치못했다

요즘 초등학생들은 천재들밖에 없나..?

 

나때는 말이야.. 초등학생때는 크레이지 아케이드, 카트라이더밖에 할 줄 몰랐는데!

>깨달은점

갈길이 멀다..

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long long dp[81] = { 1, 1, };

long long fibo(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (dp[n] != 0)return dp[n];

    for (int i = 2; i <= 80; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main()
{
    int n;

    scanf("%d", &n);
    fibo(n);

    printf("%lld\n", (dp[n - 1] * 2) + (dp[n - 1] + dp[n - 2]) * 2);

    return 0;
}