제가 속했던 팀(the pulza)가 안드로메다로 여행을 떠난 이유 중 하나는 바로 이문제 때문이 아니었을까 싶습니다(실제로도 대회에서는 풀지 못했고, 대회가 끝나고 알고스팟의 중계를 보고 난 직후에야 풀게 되었던 문제입니다.)
하지만 statistics를 봤을 경우 참가한 팀 중에서 21팀이 풀었던 문제인지라 난이도는 그리 어렵지 않다라고 평가를 할 수 있을듯 합니다.
처음에 봤을 때 ICPC계에서 조금이라도 발을 붙이신 분이라면 떠올랐을 문제가 있을 겁니다.
혹시 이 문제를 풀지 못하셨던 분이라면 먼저 추천해드리고 싶은 문제가 있습니다. 아직도 푸시지 못하신 분은 이 문제 부터 풀어보시길 바랍니다.
Tiling : http://acm.pku.edu.cn/JudgeOnline/problem?id=2506
위의 문제는 동적계획법으로 풀 수 있으며, 이 문제를 풀기 위한 점화식은 다음과 같습니다.

마지막으로 남은 것은 대칭을 이루는 모양의 가지수 인데요. 길이 N에 대해서 대칭을 이루는 경우의 수는 다음과 같이 구합니다(여기서 문제 조건을 고려하지않은 길이 N에 대한 모든 경우는 P[N]으로 표기합니다.)
우선 길이가 홀수 일경우엔 1 x 2 타일이 가운데에 세워져 있는 모양일 경우를 기준으로 대칭이 되기 때문에 P[(N-1)/2] 가 대칭을 이루는 경우가 됩니다.
짝수의 경우엔 절반의 모양이 대칭이 되는경우와, 1 x 2 타일이 2개가 눕혀진 모양으로 2 x 2 크기로 가운데에 존재하는 경우 혹은 2 x 2 타일이 가운데에 위치한 경우가 존재하므로 가지수는 P[N/2] + 2 * P[(N-2)/2]가 됩니다.
이것만 해결하면 아래와 같이 간결한 소스코드가 나오게 됩니다. 대회에서 못푼 문제라는 점이 아쉽긴 하지만, 꽤나 재미있는 문제 중에 하나가 아니었나 싶습니다.

#include <iostream>
using namespace std;
typedef long long ll;
ll p[31]; // 문제 조건을 고려하지 않은 가지수를 저장한 테이블
ll d[31]; // N에 대한 답을 저장하는 테이블 
void prepare() {
    p[1] = 1; p[2] = 3;
    for(int i=3;i<=30;++i) p[i] = p[i-1] + p[i-2] * 2;
    d[1] = 1; d[2] = 3;
    for(int i=3;i<=30;++i) {
        ll B;
        if(i%2==1) { B = p[(i-1)/2]; }
        else { B = p[i/2] + 2 * p[(i-2)/2]; }
        d[i] = (p[i]-B) / 2 + B;
    }
}
int main() {
    prepare();
    int T, N;
    cin >> T;
    while(T--) {
        cin >> N;
        cout << d[N] << endl;
    }
}