[python] 백준 11727 - 2xn 타일링 2
출처 : 백준 https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
먼저, 생각해야 할 부분
1. 전형적인 DP 문제이다.
DP는 최솟값, 최댓값을 찾거나 혹은 특정 조건을 만족하는 해의 개수를 찾을 때 주료 사용되는데,
이 문제는 특정 조건을 만족하는 해의 개수를 찾는 Counting 문제이다.
DP에서 규칙을 찾아내기 좋은 방법은, 바로 한 단계 전을 생각하는 것.
n번째 블록에서 블록이 추가되기 전을 생각하며 규칙을 찾아보자.
풀이
n = int(input())
dp = [1 for _ in range(n+1)]
for i in range(2, n+1):
dp[i] = (dp[i-1] + dp[i-2]*2) % 10007
print(dp[n])
규칙을 찾기 위해서는 한 단계 전을 생각해보아야한다.
블록에는 1칸짜리 블록, 그리고 2칸짜리 블록이 있으므로 생각해 볼 수 있는 전 단계는
1. 길이가 1만큼 짧은 경우
2. 길이가 2만큼 짧은 경우
이다.
1. 길이가 1만큼 짧은 경우
길이가 1만큼 짧을 경우 추가될 수 있는 블록은 1칸짜리 블록이 세로로 들어오는 경우 밖에 없다.
2. 길이가 2만큼 짧은 경우
길이가 2만큼 짧은 블록에서 추가될 때는 위의 그림과 같이 3가지 경우 케이스를 생각해볼 수 있다.
위 중 첫 번째 1칸 블록 2개가 세로로 추가되는 첫 번째 경우는 F(n-1)에서 1칸 블록을 세로로 붙이는 것과 겹친다.
따라서 1칸 블록을 가로로 2개 추가하는 경우, 2칸 블록을 1개 추가하는 경우가 F(n)에 해당한다.
이를 종합해보면 F(n) = F(n-1) + 2 * F(n-2)라는 점화식을 얻을 수 있다.
시간 복잡도
O(N)
알게 된 점
DP는 한 단계 전을 생각하자.
DP에서 규칙을 찾는 방법 중 대표적인 방법이다.
고찰
-
Github