문제 링크
https://www.acmicpc.net/problem/2133
🕒 Python 풀이시간: 2시간 이상
dp=[0]*31
dp[2]=3
n=int(input())
for i in range(4,31):
if i%2==0:
dp[i]=dp[i-2]*3
for j in range(4,i,2):
dp[i]+=dp[i-j]*2
dp[i]+=2
print(dp[n])3xN 타일 채우기 문제! 🧩✨
3xN인 타일을 1x2와 2x1인 타일로 채우는 모든 경우의 수를 구하는 문제이다. 딱보았을 때, 벌써 DP 문제라고 생각하고 접근하였다.
점화식을 세우는데 있어서 상당한 시간이 걸렸는데 규칙은 이와 같다. dp[n-2]의 경우를 먼저 따졌을 때, 3x2를 채우는 방법은 3가지 이기 때문에 dp[n-2]x3을 해준다. 그리고 두칸씩 더 확보하면서 따지는데 예제의 그림을 보면 3x4칸짜리 패턴이 존재하는 것을 알 수 있다. 이와 같이 아래 위로 존재하기 때문에 dp[n-4]x2가 된다고 할 수 있다. 이렇게 이러한 수를 더하면 되는데 이 때 N이 커질 수록 n-k(k는 짝수)의 연결되어 있는 패턴, 즉 3x2로는 만들어지지 않는 이어져있는 패턴이 2개씩 생겨나기 때문에 각 이전의 dp[n-k]에 2를 곱하여 더해주면 된다.
마지막 경우에는 결국 2개가 남기 때문에 2를 더해주면 된다. 여기서 2는 특수패턴을 처리하는 경우이다. 즉 전체의 경우를 잇는 특수패턴인 것이다. 아까 말했던 예제의 가로가 4칸짜리 패턴도 dp[4]에서의 아래, 위를 뒤집은 것을 포함해 패턴이 2개 나오는 식인 것이다.
이렇게 Python으로 백준의 "타일 채우기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
