백준 11727: 2xn 타일링(2) 해설- python

✏️ 문제

11727번: 2×n 타일링 2

11727

 

✏️ 풀이

2xn 타일링 문제에서 2x2타일이 추가된 형태의 문제로 점화식만 살짝 수정해주면 된다.

2xn 타일링 문제는 아래에서 다시 풀어보자

백준 11726: 2xn 타일링 해설- python

 

이전의 문제에서는 점화식이 cache[n] = cache[n-1] + cache[n-2] 꼴이었다.

세로로된 타일이 하나 존재할때 2x(n-1)로 된 영역 을 채우는 경우의 수를 고려하고 

가로로 누운 타일이 두개 쌓여있을때는 2x(n-2)로 된 영역 을 채우는 경우의 수를 고려해 둘을 더하는 형태였다.

이번 문제에서 바뀐 것은 무엇인가? <가로로 누운 타일이 두개 쌓여있는 경우> 가 <2x2 타일이 하나 있는 경우>로 대체될 수 있게 된 것이다. 따라서 점화식은 아래와 같이 바꿀 수 있다.

 

cache[n] = cache[n-1] + cache[n-2]*2

 

(Python)

n = int(input())
# memoization을 위함
cache = [0]*1001
# n이 1,2인 경우는 명확하니까 미리 선언해둔다.
cache[1]=1
cache[2]=3
# dynamic programming
for i in range(3,1001):
  cache[i] = (cache[i-1]+cache[i-2]*2)%10007

print(cache[n])