[백준] 11727 - 2xn 타일링 2

아이데이션

앞서 풀었던 2xn 타일링 문제에서 조건 하나가 추가된 버전이다.

앞선 문제와 마찬가지로 다이나믹 프로그래밍을 이용하여 풀었다

다만, 2x2 타일이 추가 되었기 때문에 해당 조건을 고려해주기 위하여,

1. n - 1까지 쌓은 상태에서 2x1 타일을 하나 쌓기

2. n - 2까지 쌓은 상태에서 2x1 타일을 두개 쌓기

의 2번 조건을 다음과 같이 수정하였다.

 

2-1. n - 2까지 쌓은 상태에서 2x1 타일을 두개 쌓기

2-2. n - 2까지 쌓은 상태에서 2x2 타일을 두개 쌓기

 

2의 갈래가 두가지로 나눠졌기 때문에 cache[i - 2] * 2를 해주었다.

 

풀이

 

n = int(input())
cache = [1] * (n + 1)

for i in range(2, n + 1, 1):
    cache[i] = cache[i - 1] + cache[i - 2] * 2

print(cache[n] % 10007)