[Python] 백준 11727번_2xn 타일링 2

문제 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

코드

num = int(input())
way = [0]*(num+1)

for i in range(1, num+1): #입력값이 1일때 index error를 방지하기 위해 for문 안에서 함께 처리
    if i == 1:
        way[i] = 1
    elif i == 2:
        way[i] = 3
    else:
        way[i] = way[i-1] + way[i-2]*2
print(way[num]%10007)

풀이 

• 풀이 진행 방법은 그 전 문제인 2xn타일링 1과 유사하다.
  
  • 2xn 타일링 1 : https://c-omealong.tistory.com/35?category=1033222

• 차이점은 2*2 블럭이 아예 별도의 블럭으로 추가가 되었다는 것. 따라서 1*2블럭 2개인 1set과 2*2블럭을 구분해야 함 
  • 동일하게 way[n] = way[n-1] + way[n-2] 틀에서 출발함
  • 이때, 가로길이 n개와 1개 차이나는 블럭은 어차피 2*1밖에 못오기에 그대로 진행됨
  • 하지만 n과 2차이나는 way[n-2]의 경우 (1) 1*2블럭 X 2개가 오는 경우, (2) 2*2블럭 X 1개가 오는 경우 이렇게 경우의 수를 2배로 고려해줘야 함
  • 따라서 점화식으로 way[n] = way[n-1] + 2* way[n-2] 가 도출된다.