[JAVA] 백준 (골드4) 2133번 타일 채우기

링크

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

---

입력 예제

2

---

출력 예제

3

---

풀이

dp 배열은 다음과 같이 정의한다.

dp[i]: 3 X i 크기일 때 타일을 채우는 경우의 수

N = 2

우선 간단히 생각해봐도 가로가 홀수일 때는 타일을 놓을 수 없다. N = 2일 때부터 생각해보면 다음과 같이 3가지의 경우의 수가 나온다. (dp[2] = 3)

N = 4

N = 4일 때는 N = 2일 때 경우의 수를 이어 붙히면 된다. 그래서 dp[4] = 3 * 3이 되고, N = 4일 때만 만들어지는 특수한 모양이 2개가 나오므로 최종적으로 dp[4] = 11이 된다.

N = 6

N = 6일 때는 마찬가지로 N = 4일 때 N = 2일 때 경우의 수를 이어 붙히면 된다. (dp[6] = dp[4] * dp[2] = 33) 하지만 이때는 N = 4일 때 특수한 모양의 왼쪽에 N = 2를 붙히는 경우는 고려되지 않았으므로 dp[6] += dp[2] * 2(특수한 모양))이 되고, N = 6일 때도 특수한 모양 2개가 존재하므로 최종적으로 dp[6] = 41이 된다.

N = 8

동일하게 N = 8일 때를 생각해보면 그림과 같고,

점화식은 다음과 같다.
dp[n] = dp[n-2] * dp[2] + Σ(dp[n-k] * 2)(k=4, 6, 8, ...)

이것을 코드로 구현하면 다음과 같다.

dp[0] = 1;  //놓을 수 없는 경우 1
dp[2] = 3;

for (int i = 4; i <= N; i += 2) {
    //dp[i-2] 타일에 dp[2]을 오른쪽에 붙힌다.
    dp[i] = dp[i - 2] * dp[2];
    //특수한 모양에 대해 추가적인 계산
    for (int j = i - 4; j >= 0; j -= 2) {
        dp[i] += dp[j] * 2;
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        if (N % 2 != 0) {  //N이 홀수일 때
            System.out.println(0);
            return;
        }

        int[] dp = new int[N + 1];

        dp[0] = 1;  //놓을 수 없는 경우 1
        dp[2] = 3;

        for (int i = 4; i <= N; i += 2) {
            //dp[i-2] 타일에 dp[2]을 오른쪽에 붙힌다.
            dp[i] = dp[i - 2] * dp[2];
            //특수한 모양에 대해 추가적인 계산
            for (int j = i - 4; j >= 0; j -= 2) {
                dp[i] += dp[j] * 2;
            }
        }

        System.out.println(dp[N]);
    }
}