24. 2133번 타일 채우기

 

 

여타 다른 DP문제들 처럼 1부터 차근차근 실행해보며 규칙을 찾아봤다

 

N이 1일땐 

3x1 크기의 벽 경우의수 0

 

N이 2일땐

3x2 크기의 벽 경우의수 3

N이 3일땐

3x3 크기의 벽 경우의수 0

 

N이 4일땐

3x4 크기의 벽 경우의수는 3x2의 벽이 2개가 붙어있다고 생각하면 편하다

그러면 9가지 경우의 수에 추가적으로 

이런 특수한 형태 2가지가 생겨 총 11가지의 경우의 수가 생긴다

 

N이 5일땐 

3x5 크기의 벽 경우의수 0

 

N이 6일땐

3x6 크기의 벽 경우의 수는

1.3x4의벽 과 3x2의벽

2.3x2의벽 과 3x4의벽

3.3x6의 벽으로 나눌수 있겠는데

 

1번의 경우에는 3x4의벽의 가지수인 DP[4]와 3x2의벽의 가지수인 DP[2]를 곱해주면

11x3 = 33가지의 경우의 수

 

2번의 경우에도 DP[2]와 DP[4]의 곱으로

3x11 = 33가지의 경우의 수

다만 1번 2번의 경우 중복된 경우의 수가 나올 수 있다 때문에

DP[4]의 특수한 형태 일때만 더해주면된다

즉, DP[2] x DP[4의 특수형태]

3x 2 = 6

 

3번의 경우 이미 중복된것은 1,2번에서 다나왔기 때문에 N6의 특수형태만 더해주면된다

N이 4일때와 마찬가지로 특수한 형태를 찾아보면

이런 형태가 나온다

따라서 2가지의 경우의 수가 추가되고

 

결과적으로 33 + 6 + 2 로 41가지의 경우의 수를 가진다

 

 

점화식

n이 6이될때까지 수기로 해본결과 우리가 알수 있었던 점은

1. n이 홀수 일때는 경우의 수가 나올 수 없다

전체칸은 홀수인데 채워지는 2x1 1x2 벽들의 합은 짝수이기에 짝수로 홀수를 만들 수는 없기 때문이다

 

2. n이 짝수 이면서 4 이상일 경우에는 특수한 형태의 경우의 수가 생긴다

 

위의 N이 6일때로 만들어본다면

DP[6] = DP[4]*DP[2] +

- 위 N이 6일때의 예시 1번 11*3

DP[6] = DP[4]*DP[2] + DP[2]*2

- 위 N이 6일때의 예시 2번 3*2

DP[6] = DP[4]*DP[2] + DP[2]*2 + DP[0]*2

- 위 N이 6일때의 예시 3번 1*2

 

이 되겠고 이는 각각 33 + 6 + 2 가 되어 총 41 가지의 경우의수 가 모두 나오게된다.

 

이를 고려하여 점화식을 만들어보면 

DP[N] = DP[N-2]*DP[2] +DP[N-4]*2 + DP[N-6]*2 + DP[N-8]*2 + DP[N-10]*2 + ....

가 되겠다.

-DP[4] 부터 특수한 형태가만들어진다 때문에 사실상 식은

DP[N-2]*DP[2] 는 고정이며 이후 들어올 (N-4,N-6....)*2 로 봐도 무방하다.

 

그럼 코드를 작성해보자

 

코드작성

import java.io.*;

public class training {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] DP = new int[N + 1];

        DP[0] = 1;
        DP[2] = 3;

        for(int i=4; i<=N; i+=2){
            DP[i] = DP[i-2] * DP[2];
            //DP[N-2]*DP[2]
            for(int j=i-4; j>=0; j-=2){
                DP[i] = DP[i] + DP[j]*2;
                //기존값에 특수한 형태를 더해주는 계산
            }
        }
        
        System.out.println(DP[N]);
    }
}