[🥈1 / 백준 2133 / 파이썬] 타일 채우기

 

2133번: 타일 채우기

 

문제

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

입력

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

출력

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

 

예제 입력 2

예제 출력 3

 

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

 

풀이

 

전형적인 동적 계획법 문제인데, 주어진 데이터가 얼마 없어 직접 찾는 것이 조금 힘들다.

 

타일은 무조건 넓이 2 짜리이기 때문에 벽의 길이가 홀수일 경우 절대로 만들 수 없다.

따라서 n이 홀수일 경우엔 0을 출력하면 된다.

 

그럼 점화식을 찾기 위해 작은 단위부터 경우의 수를 직접 찾아보도록 하자.

 

 

3 x 2

 

예제에 나와 있듯 3가지 경우의 수가 있다.

직접 그림을 그려 확인해보면 아래와 같다.

 

 

3 x 4

 

위에서 3 x 2 의 경우의 수는 3 가지라고 구했다.

따라서 3*3 을 해준다.

 

단, 여기서 조심해야 할 것은 3 x 4 일 때에만 만들 수 있는 모양이 있다는 것이다.

그 모양은 아래와 같다.

 

이렇게 2 가지가 있다. 따라서 3 x 4의 경우의 수는 3*3 + 2 인 11이 된다.

 

3 x 6

 

3 x 4에서 2 만큼 열 너비를 늘렸으므로 3 x 4 의 경우의 수 * 3 x 2 의 경우의 수를 해주자.

 

33 경우의 수

위 경우의 수는 3 x 4 블럭이 왼쪽에 있을 때에만 해당한다.

오른쪽으로 두었을 때의 경우의 수도 구해주도록 한다.

 

다만, 겹치는 경우의 수가 굉장히 많다.

겹치지 않는 경우의 수만 구해서 더해주면 되는데, 그 경우의 수는 아래와 같다.

 

6 경우의 수

 

이제 3 x 6 일 때에만 만들 수 있는 경우의 수를 더하면 된다.

이는 아래와 같다.

 

2 경우의 수

 

위 경우의 수를 모두 더하면 41이 나온다.

 

 

위의 과정을 거치며 총 3가지 규칙을 찾을 수 있었다.

1. dp[n-2] * 3
2. dp[n-i] * 2 (i > 4)
3. 2

위 3가지 규칙을 통해 나온 경우의 수들을 모두 더하는 코드를 작성해주면 된다.

 

n = int(input())
# n+1은 1이 입력될 경우 dp[2]가 인덱스를 초과하게 되므로 
# n+2로 충분히 크게 만들어주자.
dp = [0] * (n+2)
dp[2] = 3

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