문제
접근
DP 문제이다.
바로 앞에서 푼 문제랑 동일하다.
이 문제 역시 타일을 뒤에만 이어붙이는 식으로 해결한다.
DP[i]는 DP[i-2]에 가로 타일 두개를 붙이거나, DP[i-1]에 세로 타일 한개를 붙이면 된다.
코드
- 파이썬 코드
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]) % 10007
print(dp[n])