1793번: 타일링

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


$O(NL+t)$ // N,L은 각각 최댓값

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string f(string a, string b) {
    int t = 0;
    string r;
    while (!a.empty() || !b.empty() || t) {
        if (!a.empty()) t += a.back() - '0', a.pop_back();
        if (!b.empty()) t += b.back() - '0', b.pop_back();
        r += t % 10 + '0';
        t /= 10;
    }
    reverse(r.begin(), r.end());
    return r;
}
string dp[251] = { "1","1" };
int n;
int main() {
    for (int i = 2; i <= 250; i++) dp[i] = f(f(dp[i - 2], dp[i - 2]), dp[i - 1]);
    while (cin >> n) cout << dp[n] << endl;
    return 0;
}