[백준] 2133번 문제 (타일 채우기) 파이썬(Python) 풀이

n = int(input())

dp = [0] * 31
dp[0] = 1
dp[2] = 3

if n % 2 != 0:
    print(0)
else:
    for i in range(4, n + 1):
        dp[i] = dp[i - 2] * 3
        for j in range(i - 4, -1, -2):
            dp[i] += dp[j] * 2
    print(dp[n])

https://honggom.tistory.com/84

[백준] 11726번 문제 (2 x n 타일링) 파이썬(Python) 풀이

https://honggom.tistory.com/85

[백준] 11727번 문제 (2 x n 타일링 2) 파이썬(Python) 풀이

위 두 문제를 풀어본 경험으로 매우 유사한 문제라고 생각했다.

그래서 해당 숫자에 대하여 경우의 수를 구하기 시작했다.

 

일단 숫자가 홀수인 경우에는 타일이 채워질 수 없으니 경우의 수가 0이다.

이어서 경우의 수를 하나씩 구해보면 아래와 같다.

n	n에 대한 경우의 수
1	0
2	3
3	0
4	11
5	0
6	41
7	0
8	153
9	0

(물론 경우의 수를 다 구해보지는 않았다. 11개도 힘든데 41개를 그려볼 생각은 없었다.)

 

참고로 dp[0]에 1을 할당한 이유는 아래 나올 식이 성립하기 위해서 임의로 할당해준 값이다.

 

그러면 숫자의 규칙을 알 수 있다.

dp[i] = dp[i - 2] * 3
for j in range(i - 4, -1, -2):
	dp[i] += dp[j] * 2

위와 같은 규칙으로 숫자가 증가한다는 것을 알 수 있는데.. 솔직히 이 문제는 좋은 문제인지는 잘 모르겠다.

dp로 푸는 것은 맞으나 일단 경우의 수가 너무 급속히 증가해서 경우의 수를 일일히 세어보기 어렵고, 경우의 수를 일일히 세어보지 않으면 어떤 식으로 숫자가 증가하는 것인지 알 수가 없다..