[백준 2024/10/10] 11727번 2xn 타일링 2

1. 문제

https://www.acmicpc.net/problem/11727

 

2. 접근 방법

f(n) = f(n-1) + f(n-2) * 2

라는 점화식을 생각해 낼 수 있었다.

n-1에서는 1*2 타일 하나만 선택되어서 나올 수 있으며 f(n-2)에서는 2*1과 2*2를 선택함을 통해 f(n)에 도달할 수 있다.

 

이를 이용해서 코드를 작성하게 되었다.

 

3. 코드

def get_poss(n):
    dp = [1] * 1001
    dp[2] = 3

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

    return dp[n] % 10007


if __name__ == "__main__":
    n = int(input())
    print(get_poss(n))