2xn 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제. 점화식 dp[i-1] + (dp[i-2]*2)를 사용하여 풀었다.
n = int(input())
dp = [1, 3]
for i in range(2, n):
dp.append(dp[i-1] + (dp[i-2] * 2))
print(dp[n-1] % 10007)
2020-11-19 at Algorithm category
2xn 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제. 점화식 dp[i-1] + (dp[i-2]*2)를 사용하여 풀었다.
n = int(input())
dp = [1, 3]
for i in range(2, n):
dp.append(dp[i-1] + (dp[i-2] * 2))
print(dp[n-1] % 10007)
I like to share my knowledge for those who wandering in issue.