[python] 백준 11727 - 2xn 타일링 2

출처 : 백준 https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

먼저, 생각해야 할 부분

 

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

백준 11727 - 2xn 타일링 2