[백준2133번] 타일 채우기 / Python3

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1

2

예제 출력 1

3

나의 풀이

이 문제를 풀기위해 조금이라도 생각을 해보았다면 N이 홀수일때에는 해당 타일로는 만들 수 없다는 것을 눈치를 챘을 것이다. 그럼 이제 2부터 시작하여 짝수의 경우들만 세어나가면 된다는 것이다.

우선 3*2의 경우는 아래와 같다.

이후 N이 늘어날때마다 이 모든 경우에 3개를 붙여가면서 수를 세어가면 된다. 다시말해 바로 이전의 경우의 수에 3을 곱하면 된다는 것이다. 그러나 3*4의 경우를 그려보면 아래와 같이 위의 세개를 붙여서는 나올 수 없는 경우가 나온다.

그래서 3*4를 채우는 경우의 수는 '3*2'의 경우의 수 * 3 + 2가 된다. 그럼 이렇게 이제 뒤의 모든 경우에 2를 더하면 될까? 비슷하지만 더 생각해보아야한다. 3*6, 3*8 ... 의 모든 경우에서 아래와 같이 생기기 때문이다.

따라서 앞에서 바로 이전의 경우의 수에서 3을 곱한 값에 4이상이라면 4부터는 새로운 경우가 생기기 때문에 이 모양들에 대해서도 곱해주어야 모든 경우의 수를 구할 수 있다는 것이다. 따라서 for문 안에서 이전 경우의 수에 3을 곱한 값을 저장하고 for문을 또 돌려서 4부터 2씩 증가하는 경우에 대해서도 2씩 곱해주어야 한다. 이렇게 하기위해서는 dp[0]은 꼭 1로 미리 초기화를 해놓아야 한다는 것을 주의해야한다.

코드

# 2133번 타일 채우기

# main
n = int(input())

dp = [1] * 31                            # 0번 인덱스는 1로 초기화하기 위해
if not n % 2 == 0:
    print(0)
else:
    dp[2] = 3
    for i in range(4,n+1):
        dp[i] = dp[i-2] * 3     # 보통의 경우

        for j in range(4,i+1,2):  # 가운데가 1*2로 차는 경우
            dp[i] += dp[i-j] * 2
    print(dp[n])