[BAE/<JOON> 문제풀이] 2133. 타일 채우기 (DP.028)

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

2133번: 타일 채우기

5항까지 수기계산하고 규칙찾는데 규칙이 5~6개는 나왔다.

 

6항부터는 수기계산이 힘들어서 그냥 채점 박치기 했다. 

 

이런거 대회문제에 나오면 시간 진짜 많이 잡아먹힐거 같다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n % 2 == 1) {
        cout << 0;
        return 0;
    }
    n /= 2;
    vector<unsigned long long> arr;
    vector<unsigned long long> m;
    arr.resize(n + 1);
    m.resize(n + 3);
    arr[0] = 1;
    arr[1] = 3;
    m[0] = 1;
    m[1] = 1;
    m[2] = 1;
    for (int i = 3; i <= n; i++) {
        m[i] = m[i - 1] + m[i - 2] + 1;
    }
    for (int i = 2; i <= n; i++) {
        //arr[i] = (arr[i - 1] + arr[i - 2]) * 3 - m[i - 1];
        arr[i] = arr[i - 1] * 3 + (arr[i - 1] - arr[i - 2]);
    }
    cout << arr[n];
    return 0;
}