1720 타일코드

#include <stdio.h>
 
long long dp[1005] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    if (n == 1) {
        printf("1");
        return 0;
    }
    else if (n == 2) {
        printf("3");
        return 0;
    }
 
    dp[1] = 1;
    dp[2] = 3;
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2);
    }
    
    long long rst, minus;
    if (n % 2 == 0) {
        minus = dp[(n - 2) / 2] * 2 + dp[n / 2];
    }
    else {
        minus = dp[n / 2];        
    }
    rst = (dp[n] + minus) / 2;
    printf("%lld", rst);
}
 

1. 중복된 경우를 제거하기 위해, (전체 경우의 수 + 대칭코드)/2  연산을 해준다는 것

2. n==1,2 일 경우 따로 계산을 해준다는 것

이 두 가지가 핵심 포인트였다