(C++) - 백준(BOJ) 13301 : 타일 장식물

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

13301번: 타일 장식물

피보나치 수열을 구현하고 이를 응용해 푼 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

항 n, 정답 ans, 피보나치 수열을 저장할 일차원 배열 fibo를 선언한 후 n에 입력받습니다.

📔 풀이과정

*n이 80까지이므로 해당 피보나치 수열 값을 구할 경우 2300조 정도로 int범위를 초과할 수 있습니다. long long으로 변수들을 선언해 줘야 합니다.

x항의 피보나치 수열값을 반환하는 재귀함수 getFibo를 선언합니다. 값을 한 번만 수행하는 memoization기법을 이용해 O(n)시간에 수열값을 구할 수 있도록 구현합니다. 그렇지 않으면 O(2^n)로 n이 30중반만 넘어가도 O(1억)이 넘어가므로 시간초과(1초 초과)를 받을 수 있습니다.

n이 1일 때 ans = 4입니다. 이 후 답을 구하는데 일정한 공식이 있습니다. 바로

이전 둘레길이 + 그 다음 피보나치 수열값을 한 변으로 가진 정사각형 길이 * 2입니다.

for loop를 2 ~ n까지 수행하며 다음 공식을 적용한 결과를 ans에 누적해 더해줍니다.

📔 정답출력

 

---

📕 Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, ans = 4, fibo[81];

ll getFibo(ll x){
    if(x == 1 || x == 2) return fibo[x] = 1;
    ll &ret = fibo[x];
    if(ret != -1) return ret;
    return ret = getFibo(x-1) + getFibo(x-2);
}

int main(){
    memset(fibo, -1, sizeof(fibo));
    cin >> n;

    for(int i = 2; i <= n; i++){
        ll length = getFibo(i);
        ans += length * 2;
    }
    
    cout << ans;
}