백준 11726번 2XN 타일링 - Python

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

 

위 문제를 직접 그려보면서 점화식을 구했습니다. 

사실 이렇게 구해지는데에는 이유가 있습니다. N이라는 열중에서 가로길이가 1인 블럭 1개를 고르게 되면 F(n-1)개로 만들수 경우의 수에 블럭 1개를 더해서 만든 경우가 됩니다. 열중에서 가로길이가 2인 블럭 1개를 고르게 되면 나머지 가로 길이를 충족하는 블럭으로 채울 수 있는 경우의 수는 F(n-2)개로 만든 경우의 수에 가로 길이가 2인 블럭을 붙인 경우로 보게 됩니다. 

즉 내가 원하는 열이 N인 블럭으로 만들 수 있는 경우의 수는 F(n-1)+F(n-2)가 됩니다. 왜 N-3이나 N-4는 안 하는가?라고 생각이 들 수 있는데 3과 4도 결국에는 1과 2로 조합해서 만들어지기 때문에 점화식은 n-1, n-2로 식이 구성되는 것 입니다. 

쉽게 생각하자면 홀수와 짝수의 근간이 되는 수 1과 2가 있다면 3,4 는 별도로 주어지지 않아도 더하면 만들 수 있는것 아닌가?!와 같다고 생각하면 될 거 같습니다. 

 

위 점화식을 코드로 변환시키면 됩니다. 다만 위 문제에서 굉장히 커진 값이 오버플로 발생 시킬 것을 고려해서 10,007로 나눈 나머지를 값으로 집어넣도록 했습니다.

코드는 다음과 같습니다. 

import sys

N = int(sys.stdin.readline().strip())
ans = [0, 1, 2]
for i in range(3, 1001):
    ans.append((ans[i - 2] + ans[i - 1]) % 10007)

print(ans[N])