문제

2×n 타일링

풀이

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수에 대한 점화식을 세울 수 있습니다

• n 이 1인 경우 직사각형의 타일을 체우는 방법 - 1개
• n 이 2인 경우 - 2개
• n 이 3일경우 부터 규격화된 방식이 존재할 수 있습니다.
  - 1 x 2의 타일을 세개로 놓는 방법 - 1개
  • 2 x 1의 타일 두개와 1 x 2 타일 한개를 사용하는 방법
    • 이방법은 1 x 2 타일을 가장자리인 왼쪽, 오른쪽에 한개씩 두고 나머지를 위치하는 방법 - 2개

입니다 3부터 해당되는 점화식을 작성하도록 합니다.
n은 n번째 올 블록의 개수(dp[n]) 라고 생각하면 됩니다.

dp[n] = dp[n - 1] + dp[n - 2] (n>=3)

해당 점화식의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 dp에서 저장하도록 합니다

dp[i] = (dp[i - 1] + dp[i - 2]) % 10007

전체 코드

전체 코드