[BOJ] 11727. 2xn 타일링 2

Python3,DP

문제

입출력

입출력 예시

주요 포인트

dp[i] = dp[i-1] + 2 * d[i-2]
도출하기

출처: https://cijbest.tistory.com/21

n = 3일 때 보면 n = 2, n = 1일 때 쓴 타일이 그대로 들어 있다. 대신 같은 타일을 기준으로 앞뒤로 들어 간다. 따라서 dp[i-1] + dp[i-2] + dp[i-2]를 계산해야 한다.

dp 리스트 사이즈는 1001이다. (문제 조건에서 n이 1 이상 1000 이하라고 했으므로)

최종 코드

n = int(input())
dp = [0 for i in range(1001)]
dp[1] = 1
dp[2] = 3

for i in range(3, 1001):
    dp[i] = (dp[i-1] + 2 * dp[i-2]) % 10007
        
print(dp[n])

피드백

같은 타일이 반복되는 부분에 집중해서 n-1, n-2(2개)를 떠올리자