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

Try to solve 💭

2xN 타일링 1번 문제를 푼 뒤 다른 사람들의 풀이를 공부했었다. 주어진 타일에 대해서 마지막 타일을 1) 1x2, 2) 2x1, 3) 2x2 의 크기로 고정해서 경우의 수를 구하는 것이었다.
이번 문제는 위 아이디어와 같이 접근하여 풀어보았다.

Solution 💡

만약, n이 3일때 2x3의 타일이 존재한다고 하자.
마지막 타일을
1) 1x2(2개) 크기로 고정했을 때,
앞의 타일에서 구해지는 경우의 수는 2x1의 타일 가짓 수이므로 case[n-2]

2) 2x1 크기로 고정했을 때,
앞의 타일에서 구해지는 경우의 수는 2x2의 타일 가짓 수이므로 case[n-1]

3) 2x2 크기로 고정했을 때,
앞의 타일에서 구해지는 경우의 수는 2x1의 타일 가짓 수이므로 case[n-2]

즉, case[n] = case[n-1] + 2( case[n-2] ) 로 구해진다.

Code Review 🔎

n = int(input())
dp = [0, 1, 3]

for i in range(3, n+1):
  result = dp[i-1] + 2 * (dp[i-2])
  dp.append( result % 10007 )

print(dp[n])