[알고리즘] DP유형 - 백준 2133번 파이썬

 

 

www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

문제

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

 

입력

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

 

출력

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

 

예제 입력

2

 

예제 출력 

3

 

힌트

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

 

풀이

2×N 문제와 비슷할 줄 알았는데, 하나씩 직접 그려보니까 차이점이 있었다.

우선, 타일의 크기가 2×1, 1×2 두 가지인데, 이 타일로는 N이 홀수일 땐 벽을 완벽히 채울 수 있는 경우가 없다.



따라서 N이 홀수면 무조건 dp[N] = 0 이다.

 

이제 N이 짝수일 때를 살펴보자.

 

N = 2일 때

>> dp[2] = 3

 

 

N = 4일 때는

N = 2일 때의 3가지를 가지고 3×4를 채우면 3*3 가지

여기에 아래 그림 2가지를 더해서

따라서 dp[4] = d[2] * 3 + 2 = 11

 

 

N = 6일 때는

 - (6-2)까지 채웠다고 하고 나머지 3X2를 채우는 방법의 수는 dp[6 - 2] * 3

 - (6-4)까지 채웠다고 하고 나머지 3X4를 채우는 방법의 수는 dp[6 - 4] * 2

 위 경우에 아래 경우 2가지를 더해서

따라서 dp[6] = dp[6 - 2] * 3 + dp[6 - 4] * 2 + 2

 

 

이 규칙을 바탕으로 코드를 구현하면 다음과 같다.

 

 

코드

n = int(input())


# DP 테이블 초기화
dp = [0] * 31
dp[2] = 3

'''
# 규칙
# dp[4] = dp[4 - 2] * 3 + 2
# dp[6] = dp[6 - 2] * 3 + dp[6 - 4] * 2 + 2
# dp[8] = dp[8 - 2] * 3 + dp[8 - 4] * 2 + 2
'''

# n이 홀수일 경우 결과는 무조건 0
if n % 2 != 0:
    dp[n] = 0


# n이 짝수일 경우
else:
    for i in range(4, n + 1, 2):
    
    	# 첫 항(dp[i - 2] * 3)과 마지막 항(2)의 합을 먼저 dp[i]에 넣는다
        dp[i] = dp[i - 2] * 3 + 2
        
        for j in range(4, i, 2):
            dp[i] += dp[i - j] * 2


print(dp[n])