[Algorithm]Baekjoon 13301번 :: 타일 장식물

https://www.acmicpc.net/problem/13301

13301번: 타일 장식물

 
 
int n;
long long dp[81] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    dp[1] = dp[2] = 1;
    
    cin >> n;
    
    for (int i = 3; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
 
    cout << 2 * (dp[n] + dp[n - 1]) + 2 * dp[n];
}

 

문제에서의 도형이 구성되는 원리는, 피보나치수열의 공식으로 이루어져 있다.

그리고 최종적으로 구성되는 직사각형을 보면 가로,세로중 둘 중 하나는 dp[i] - dp[i-1]값으로 되어있고 나머지 하나는 dp[i]이기 때문에, 각각 2를 곱해서 더해주면 둘레길이를 알 수 있다.