솔직히, dp보다도 구현하는 게 빡셌던 문제같다. 풀면서 부족함을 느꼈다. string + string = string 의 더하기를 직접 구현해야했는데, 중구난방 코드가 됐다. 아래에 참고할만한 좋은 블로그의 링크를 첨부한다. string 더하기 코드를 단 몇 줄만에 짜는 걸 보고 현타가 왔다. 다음에 다시 풀어봐야겠다.
[https://jaimemin.tistory.com/618]참고할만한 블로그 바로가기
// 타일링
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int n;
vector<string> dp(251, "");
int main()
{
dp[0] = "1";
dp[1] = "1";
dp[2] = "3";
int cnt = 0;
while (cin >> n)
{
if (dp[n] != "")
{
for (int i = dp[n].length() - 1; i >= 0; i--)
{
cout << dp[n][i];
}
}
else
{
for (int i = 3; i <= n; i++)
{
string temp;
int a, b;
int pl = 0; // 올림 체크
for (int j = 0; j < dp[i - 2].length(); j++)
{
a = (dp[i - 2][j] - '0') * 2;
if (pl > 0)
{
a++;
pl = 0;
}
if (a >= 10)
{
pl++;
a = a - 10;
}
temp.push_back(a + '0');
// cout << "a:" << temp << endl;
}
if (pl == 1)
temp.push_back('1');
pl = 0; // 올림 체크
int len = max(dp[i - 1].length(), temp.length());
// vector<char> result(1000,0);
string result;
for (int j = 0; j < len; j++)
{
if (dp[i - 1][j] && temp[j])
{
a = dp[i - 1][j] - '0' + temp[j] - '0'; //10진수 계산
if (pl == 1)
{
a++;
pl = 0;
}
if (a >= 10)
{
pl++;
a = a - 10;
}
result.push_back(a + '0');
}
else if (dp[i - 1][j])
{
a = dp[i - 1][j];
if (pl == 1)
{
a++;
pl = 0;
}
if (a >= 10)
{
pl++;
a = a - 10;
}
result.push_back(a + '0');
}
else
{
a = temp[j];
if (pl == 1)
{
a++;
pl = 0;
}
if (a >= 10)
{
pl++;
a = a - 10;
}
result.push_back(a + '0');
}
}
if (pl == 1)
result.push_back('1');
dp[i] = result;
}
for (int i = dp[n].length() - 1; i >= 0; i--)
{
cout << dp[n][i];
}
}
cout << endl;
}
}