[이코테 실전문제] 바닥공사 - python

바닥공사

문제

2 X N의 바닥을 1 x 2, 2 x 1, 2 x 2 로 채운다고 할 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 구하시오.

바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력할 것

제한사항

• 1 <= N <= 1,000

풀이

왼쪽부터 타일을 채운다고 생각해보기

즉 dp[i] = dp[i - 1] + 2 * dp[i - 2] 이다.

n = int(input())
dp = [0] * 1001
dp[1] = 1
dp[2] = 3
​
for i in range(3, n + 1):
  dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 796796
​
print(dp[n])