코드

n = int(input())

d = [0] * (1001)

d[1] = 1
d[2] = 3
d[3] = 5

for  i in range(4, n+1):
    d[i] = d[i-1] + 2 *d[i-2]
    
print(d[n] % 10007)

문제 해설

동적 프로그래밍 참고

기본적인 타일링 문제의 심화 버전이다. 이 문제의 경우 점화식을 만드는게 살짝 어려울 수도 있다.

  1. n-1번째까지 타일이 덮여있는 경우의 수는 1x2 타일로 밖에 남은 공간을 덮을 수 없다. 즉, 2x1, 1x2 2개의 타일만 쓸 경우와 동일하다. (위의 점화식에서 d[i-1])

  2. n-2번째까지 타일이 덮여있는 경우의 수는 총 2x2의 공간을 타일로 덮어야 하는데, 이 경우 덮을 수 있는 방법이 2x1로 덮는 것과 2x2로 덮는 것 두가지가 된다. 따라서 d[i-2] * 2를 해줘야 모든 경우의 수를 계산할 수 있다.
  3. n-2번째 타일을 덮을 때 1x2 타일의 경우를 고려하지 않은 이유는, n-1번째까지 덮여있는 경우에 1x2로 n번째 타일을 덮는 경우에 처리되므로 따로 고려해줄 필요없다.

댓글남기기

참고