< DP > 2133번 타일 채우기 with 파이썬

문제

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

입력

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

출력

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

정답비율

35.228%

알고리즘 분류

 #DP #다이나믹프로그래밍

 

n = int(input())
dp = [0 for _ in range(31)]
lst = [2 for _ in range(31)]
lst[2] = 3
dp[0] = 1
for i in range(2, n+1, 2):
    for j in range(0,i,2):
        dp[i] += dp[j] * lst[abs(i-j)]
print(dp[n])

 

 - 생각보다 애먹었던 문제이다. 처음에는 단순하게 2일경우가 3이고, 4일 경우는 2에서의 각각의 경우에 2일경우가 곱해져서 9일것이라고 생각하고 제출했다. 즉 단순히 3의 n제곱으로 제출한 것이다.

 

 - 그러나 간과한 부분이 있었는데 가로가 4일경우, 완전히 윗줄을 가로로 눕힌걸로만 채운 경우와 아랫줄을 완전히 가로로 눕힌걸로만 채운 경우인 2가지가 더 추가가 된다. 이는 6에서도 8에서도 2개씩 나타난다. 이를 유니크한 경우로 보고 lst에 저장하였다. 이 때, 2의 경우만 3개이다.

 

 - for 문을 돌면서, 가로가 완전히 n인 경우를 곱하면서 돌았다. 이 의미는 다음과 같다.

(1 * 유니크한 가로 n인경우(2개) ) + (가로2인경우 * 유니크한 가로 n-2인경우(2개) ) + (가로4인경우 * 유니크한 가로 n-4인경우(2개) ) ..... + (가로n-2인경우 * 유니크한 가로 2인경우(3개) ) 

 

 - n이 8일 경우를 예시로 보면 다음과 같다. (dp[6] = 41, dp[4] = 11, dp[2] = 3)

 (1 * 2) + (3 * 2) + (11 * 2) + (41 * 3) = 153

 

 - 처음에 1을 곱해야하므로 dp[0] 에 1을 할당해야한다. (n이 1 이상이라는 조건이 있으므로 1을 할당하여도 문제없다.)

 

 

---

 

 

참고

 

2133번: 타일 채우기