[Python Algorithm] 2×n 타일링 2 BOJ #11727

문제

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

11727번: 2×n 타일링 2

 

내 문제 풀이

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

👉 DP 문제로, 점화식 / 메모이제이션 사용해주면 된다.

p[n] = p[n-1] + p[n-2]*2 의 점화식에 맞게 풀어주었다.

 

💡 피드백

• 점화식 문제지만, n에 따른 경우의 수를 구해주는데에 조금 시간을 할애해야 하는 문제였다.