[Python 백준] 11726 | 2xN 타일링

Try to solve 💭

n이 1,2,3,4 일때 까지 타일을 그려보며 가짓수를 생각해보았을 때, 순서대로 1,2,3,5 의 경우의 수가 나온다. 고정된 세로의 길이의 타일에서 가로만 늘어나는 구조이기 때문에 DP 문제일 거라 생각했다. 2x3의 타일에서는 '2x2+2x1' 의 크기로 운좋게 '2+1 = 3'가지의 값이 맞아 떨어졌지만, 4에서는 예외가 발생했다.. 겹치는 부분이 존재하기 때문에 바로 접근법을 달리했다.

n = 4일때, 타일 구조는 '2x2+2x2', '2x3+2x1' 이 가능
n = 5일때, 타일 구조는 '2x4+2x1', '2x3+2x2' 이 가능 ..
( '2x2+2x2+2x1'과 같은 구조는 더 큰 크기의 타일 구조에서 중복 추가 되므로 제외하였다. )
-> 중복되는 부분을 고정시킨 채 경우의 수를 구하면 된다.

Solution 💡

마지막 타일이
1) 2x1의 구조를 가질 때,
앞쪽에서 구할 수 있는 경우의 수는 2x(n-1)의 타일 가짓수 값이다.
2) 2x2의 구조를 가질 때,
앞쪽에서 구할 수 있는 경우의 수는 2x(n-2)의 타일 가짓수 값이다.

즉, 연산 식은 case[n] = case[n-1] + case[n-2] 과 같이 나타낼 수 있다.

Code Review 🔎

n = int(input())

case = [ 0, 1, 2 ]
mod = 10007

for i in range(3, n+1):
  result = case[i-1] + case[i-2]
  case.append(result % mod)
print(case[n])