kingsubin

import java.io.*;

public class boj_2133 {
    static long[] d;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        d = new long[n+1];
        d[0] = 1;

        for (int i = 2; i <= n; i+=2) {
            d[i] = d[i-2] * 3;
            for (int j = i-4; j >= 0; j-=2) {
                d[i] += d[j] * 2;
            }
        }

        System.out.println(d[n]);
    }
}

 

- 마지막 부분에 초점을 맞춤, 일단 n이 홀수일때는 채울 수 있는 방법이 없음

- 마지막 3x2를 채우는 방법의 수는 3가지 d[i] = d[i-2] * 3라고 생각해서 풀었으나 다른 방법이 또 있음

- 가로가 4, 6, 8, .. 일때 2가지 방법씩 더 존재하고 이것을 또 처리 해줘야함

- j = i-4 ~ 2씩 감소하며 d[i] += d[j] * 2; 로 추가 카운팅해줌