[BOJ/백준] 2133 타일 채우기

# 2133 타일 채우기

#  3*N 크기의 벽을 2*1 1*2로 채우는 경우의 수를 구해보자
# N = 1 => 0
# N = 2 => 3
# N = 3 => 0
N= int(input())
dp = [0]*31
dp[2] = 3
if N%2:
    print(0)
else:
    # 점화식
    # Dp(N) = DP(N-2)*3 + (2*Dp(N-4)+2*DP(N-6)+2*DP(2))
    for number in range(4,N+2,2):
        temp = 2
        for k in range(number-4,0,-2):
            temp += dp[k]*2
        temp += dp[number-2]*3
        dp[number] = temp
    print(dp[N])

 이런 류의 문제는 점화식을 찾아내지 못하면 힘든 문제인 것 같다.

직접 그려보고 패턴을 파악해서 점화식을 구해냈다.

 

1. N이 홀수이면 무조건 0 이다. (다 채울 수 있는 방도가 없기 때문이다.)

2. N이 짝수 일때만 구하면 되는데, 최초 값은 N=2일때 3이다.

3. N이 짝수일때 그려보면 해당 N에서만 발견되는 특정 조합이 2가지가 있다.

   - N= 6일때 다음과 같이 가운데가 가로로 누워있고, 양 끝이 세로로 세워진 케이스가 2개가 있다.

4. F(N)을 N일때 가지수라 한다면, F(N-2)*F(2) 만큼의 가지수가 생성이 된다. 이것은 왼쪽에 전체 크기의 N-2크기를 두고, 오른쪽에 크기가 (3*2) 타일을 뒀을때 생길 수 있는 가지수 이다.

5. 여기서 많이 해맸다. 우리는 기본적으로 왼쪽에 N-2 타일을 두고, 오른쪽에 2인 타일을 뒀다. 오른쪽에 타일을 뒀을때도 염두를 해야한다. 이 때 나올 수 있는것은 각 N마다 특수한 경우로 되는 2가지 일때의 모습에 오른쪽에 나머지 크기의 타일을 뒀을때이다. 

  - N이 8일때, 설명하면 다음 그림과 같다. 그림이 많이 조잡하다. 

  - 우측이 각 N에서 나오는 특수한 경우이고, 빨간색 네모만큼 놓는수 만큼 나올 수 있다.

  - 그러니 첫번째 그림은 F(2)*2 이고, 두번째 그림은 F(4) *2 이다.

       

 

위의 특징을 최종적으로 정리하면,

 

수식을 입력해본게 하도 옛날이라 개판이지만, 대략적으로 N=2일때 제외하고는 다음과 같이 진행해주면 된다.

 

 

문제 자체는 점화식인 것을  알았지만, 이에 맞는 점화식을 구하는데 너무 힘들었다. 이와 비슷한 문제를 풀어서 연습을 더 해야할 것 같다.