[백준] 2×n 타일링

# 설명

1*2, 2*1의 타일 종류를 가진 타일들로 2*n크기의 직사각형 보드를 채우는 경우의 수를 구하시오.

여기서 경우의 수를 10007로 나눈 나머지를 출력하시오.

 

# 입출력

입력 (n)	출력
2	2
9	55

 

# 문제 풀이

def tailing(n):
    memo = {0:0, 1:1, 2:2} # 타일 배치 경우의 수
    type_t = [1,2] # 타일 타입
    if n < 3:
        return memo[n]

    for N in range(3, n+1):
        n_case = 0
        for x in type_t: 
            if N >= x: # 타일을 배치할 수 있다면
                n_case += memo[N-x]
        memo[N] = n_case
    return memo[N]

n = int(input()) # 보드 너비 n
res = tailing(n)
print(res%10007)

 

# 핵심 포인트

- 동적 프로그래밍 DP