[DP] 11726번 - 2xN 타일링(38일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline
#직사각형의 세로 입력
n = int(input())
#각 세로 길이에 필요한 직사각형의 수를 저장하는 dp
dp = [0 for _ in range(n+1)]

for i in range(1,n+1):
    #세로가 1인 경우 세로 타일 사용 = 1개
    if(i == 1):
        dp[i] = 1
    #세로가 2인 경우 세로 타일과 가로 타일 사용 = 2개
    elif(i == 2):
        dp[2] = 2
    #세로가 3 이상인 경우
    #세로 길이 -1의 모양에 세로 타일을 붙이는 것과 같음
    #세로 길이 -2의 모양에 가로 타일을 붙이는 것과 같음
    #세로길이 -1의 개수와 세로길이 -2의 개수를 더해주면 됨
    else:
        dp[i] = dp[i-1] + dp[i-2]
#최종 경우의 수를 10007로 나눈 값 출력
print(dp[-1] % 10007)

#인사이트
#도형 등 시각적인 부분에 현혹되지 말것
#세로 타일과 가로 타일을 각각 +1, +2로 치환이 가능함
#결국 세로길이 N을 +1과 +2를 배치하여 만드는 경우의 수를 묻는 것이기 때문에
#1,2,3 더하기 4 유형과 같은 방식으로
#직전 길이에 +1, 직직전 길이에 +2로 새로운 모양을 생성하는 방식으로 접근