문제
접근
DP 문제이다.
기존 타일링 문제가 조금 변형 되었다.
DP[i-2]에서 DP[i]를 만드는 방법이 두 가지가 되었다.
기존에는 가로 타일 2개를 붙이는 방법만 존재했지만, 이제 2x2짜리 정사각형 타일을 붙일 수도 있다.
즉, DP[i]를 구할 때, DP[i-2]는 두배를 해주면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
n = int(input())
dp = [1] * (n+1)
for i in range(2, n+1):
dp[i] = (dp[i-1] + (dp[i-2]*2)) % 10007
print(dp[n])