[BOJ] 2718. 타일 채우기

https://www.acmicpc.net/problem/2718

접근 방법

그 전의 타일의 올 수 있는 경우에 대해 생각해봄.

그 전 타일이 올 수 있는 경우의 수는 총 5개가 나왔다.

1) 그 전의 타일이 다 채워져있는 경우 = 그 전의 타일이 하나도 채워져있지 않는 경우

2) 그 전의 타일이 밑에서 2개만 채워져있는 경우

3) 그 전의 타일이 가운데 2곳만 채워져있는 경우

4) 그 전의 타일이 위 아래 1곳씩 채워져 있는 경우

5) 그 전의 타일이 위의 2곳만 채워져있는 경우

위의 경우를 그림으로 표현을 해보았다.

---

여기서 왜

o

x

o

x 를 하지 않았냐고 물어본다면 모든 타일이 채워져야하기 때문에 불가능하다!

Need Know

1. DP

전체 코드 ( Java )

import java.io.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int T;
    static int[][] cache;

    public static void main(String[] args) throws IOException {
        set();

        System.out.print(sb);
        br.close();
    }
    static void set() throws IOException {
        T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            N = Integer.parseInt(br.readLine());
            solve();
        }
    }
    static void solve() throws IOException {
        cache = new int[N+2][5]; //

        cache[1][0] = 1;
        for(int i=2; i<N+2; i++){

            cache[i][0] = cache[i - 2][0] + cache[i - 1][0] + cache[i - 1][1] + cache[i - 1][4] + cache[i - 1][3]; // 빵꾸 X
            cache[i][1] = cache[i - 1][0] + cache[i - 1][4]; // 위의 두개가 빵꾸
            cache[i][2] = cache[i - 1][3]; // 맨위랑 맨 아래가 빵꾸
            cache[i][3] = cache[i - 1][0] + cache[i - 1][2]; // 중간 두개가 빵꾸
            cache[i][4] = cache[i - 1][0] + cache[i - 1][1]; // 밑에 두개가 빵꾸
        }

        sb.append(cache[N+1][0]+ "\n");
    }
}