알고리즘/동적프로그래밍(DP)

[Python] 백준 11727: 2xn 타일링 2 풀이

아뵹젼 2021. 1. 20.

소스코드

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

저번 문제와 동일한 구조이다.

이번에는 2x2 타일이 추가되었으므로,

dp[n-2] 에서 dp[n] 이 되기 위해선 1x2 타일 2개를 놓는 방법, 2x2 타일 1개를 놓는 방법 -> 2 * dp[n-2] 의 횟수와 동일

dp[n-1] 에서 dp[n] 이 되기 위해서 2x1 타일 1개를 놓는 방법 -> dp[n-1] 의 횟수를 더해주면 된다.

즉, dp[n] = 2 * dp[n-2] + dp[n-1]

로직이 거의 동일하여 더 이상의 설명은 생략하겠다.

자세한 설명은 11276 참고!