백준

2133번 타일 채우기 / Python

문제

풀이과정

타일이 채워지는 경우(n % 2 == 0)와 타일을 채울 수 없는 경우(n % != 0)를 분리

다이나믹 프로그래밍 사용

1. 큰 문제를 작은 문제로 나눈다
2. 작은 문제에서 구한 답은 그것을 사용하는 큰 문제에서도 동일하다.

보텀업(Bottom-Up) 방식, 상향식
작은 문제부터 아래에서 위로 올라가는 방식

반복문을 통해 작은 문제부터 답을 도출하는 방법으로 구현

DP 테이블
결과 저장용 리스트 dp_table=[0]*31

점화식
n이 짝수인 경우,
n == 2일 때 경우의 수 3
n == 4일 때, n == 2인 경우의 수 * 3(n == 2인 경우를 이어 붙인다) + n == 4일 때 모양(나눠지지 않는 모양)
...
n에 따라 등장하는 나눠지지 않는 모양 2가지 + 이전의 결과를 이어 붙인 경우

$d(n) = d(n-2) * 3 + d(n-4) * 2 + ... + d(0) * 2$

3 * 2 타일을 만드는 경우는 3
이후 나눠지지 않는 모양은 각 경우에서 2가지

소스코드

#2133번 타일 채우기
#https://www.acmicpc.net/problem/2133

n = int(input())

result=0
dp_table=[0]*31

dp_table[0] = 1

for i in range(2, n+1, 2):
  dp_table[i] = dp_table[i-2] * 3
  for j in range(0, i-2, 2):
    dp_table[i] += dp_table[j] * 2
  
if n%2 != 0:
  print(0) #타일로 벽을 채울 수 없는 경우
else:
  result = dp_table[n]
  print(result)