문제

문제 링크

문제 접근

  • 이 문제는 처음에 그냥 2칸 길이로 만드는 경우와, 4칸 길이로 만드는 경우만 가지고 풀 수 있는 문제인 줄 았았다.
  • 그래서 cnt[i] = cnt[i-1]*3 + cnt[i-2]*2로 구할 수 있을 줄 알았다.
  • 하지만 찾아보니 2칸, 4칸 일때 말고 6칸 일 때 2경우가 추가 되고 8칸일 때도 2경우가 추가되는 걸 알게 되었다.
  • 즉, 2칸일 때 만드는 경우 말고 4, 6, 8, … j칸인 경우에는 cnt[i-j]*2를 더해줘야 한다.

코드

#include <cstdio>
int cnt[16], n;
int main(){
    cnt[0] = 1, cnt[1] = 3;
    scanf("%d", &n);
    if(n%2){
        printf("0");
        return 0;
    }
    n /= 2;
    for(int i = 2; i <= n; i++){
        cnt[i] = cnt[i-1]*3;
        for(int j = 2; i >= j; j++)cnt[i]+= cnt[i-j]*2;
    }
    printf("%d", cnt[n]);
}

느낀점

  • 디피 굳!!