[BOJ] 2xn 타일링 2(11727) - PYTHON

N의 크기가 주어질 때 2 * N 사이즈의 직사각형을 (2 X 1), (1 X 2), (2 X 2)의 직사각형으로 채우는 경우의 수를 구하는 문제다. 경우의 수를 10007로 나눈 나머지를 정답으로 출력한다.

시간 복잡도: O(N)

11727번: 2×n 타일링 2

---

풀이 방법

N의 크기가 커질 때마다 채울 수 있는 경우의 수는 일정한 규칙을 가지고 증가한다. N이 1일 때부터 차례대로 확인해보자

N = 1일 때

N이 1일 때는 1X2 직사각형 한 개로 이루어진 경우밖에 없으므로 1이다.

N=2일 때

N이 2일 때는 (1X2 사각형 2개), (2X1 사각형 2개), (2X2 사각형 1개)로 이루어진 3가지 경우가 있다.

N=3일 때

N이 3일 때는 다음과 같이 5개 경우가 있다.
여기서 보면 위 3개의 도형은 N이 2일 때 만들 수 있는 경우에다가 1X2 직사각형을 붙인 형태다.
또한 아래 2개의 도형은 N이 1일 때 만들 수 있는 경우에다가 각각 2X1도형 2개, 2X2도형 1개를 붙인 형태다.

덧붙인 도형을 옆으로 조금 떨어뜨려보면 다음과 같다.

즉 N이 증가함에 따라 경우의 수는 N-1일 때 경우의 수 + 2 * (N-2일 때 경우의 수) 임을 알 수 있다.
점화식으로 구성하면 식은 다음과 같다.

점화식

---

코드

N = int(input())
 
arr = [0] * 1001
arr[1] = 1
arr[2] = 3
 
for i in range(3, N + 1):
    arr[i] = (arr[i - 1] + 2 * arr[i - 2]) % 10007
print(arr[N])

주석 추가

N = int(input())
 
arr = [0] * 1001  # N의 값은 최대 1000
arr[1] = 1  # N=1 일때 값은 1
arr[2] = 3  # N=2 일때 값은 3
 
for i in range(3, N + 1):
    arr[i] = (arr[i - 1] + 2 * arr[i - 2]) % 10007  # 이후 값은 N-1의 값 + 2 * (N-2의 값)
print(arr[N])

결괏값을 10007을 나눈 나머지로 출력해야 하는데, 이는 각 경우의 수를 구할 때마다 10007을 나눈 값으로 처리해도 같은 값이 나온다.

ex) 정답이 103이고, 나누는 수가 5라면

103 % 5 = 3이며 이는 (3 % 5 + 100 % 5) % 5, (4 % 5 + 99 % 5) % 5, (5 % 5 + 98 % 5) % 5  등과 같다.

---

채점 결과

문제 조건에 10007로 나눈 나머지를 출력해야 하는 조건을 놓쳐서 틀렸다.