[DP] 11726. 2 x N 타일링

문제 해석

---

위 문제는 DP를 연습하기 좋은, 쉬운 DP 유형입니다.

DP는 큰 문제를 유닛으로 쪼개어 풀어내고, 이를 활용하여 큰 문제의 답을 도출하는 문제 해결 기법입니다.

이 문제에서 타일을 계속 붙이는 경우의 수를 구하는데, 길이가 N인 타일을 만드는 경우의 수를 구하기 위해서는 N-2의 길이와 N-1의 길이일 때 어떻게 타일을 쌓는지를 알아냄으로써 N이 어떤 길이여도 답을 구할 수 있게 풀어낼 수 있습니다.

N-2와 N-1로 경우를 나누는 이유는, 타일의 유형이 1x2, 2x1 두 개 뿐이기 때문입니다. N-2일 때에는 1x2로 두 개를 쌓는 경우만 생각하면 되고, N-1일 때에는 2x1을 쌓는 경우만 생각하면 됩니다.

N-2일 때 2x1을 두 개 쌓는 경우도 고려해야 하는 것이 아니냐 생각하실 수 있지만, 이는 N-1이 되는 경우에 포함되므로 N-2인 상황에서는 고려하지 않아야 합니다.

풀이 코드

---

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
def dp(n):
    global dp_arr
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 2
    if dp_arr[n] != 0:
        return dp_arr[n]
    else:
        dp_arr[n] += dp(n-1) + dp(n-2)
        return dp_arr[n]


n = int(input())
dp_arr = [0] * (n+1)
print(dp(n)%10007)