[BOJ - DP] 11726번 : 2×n 타일링 ( python )

백준알고리즘 11726번 2×n 타일링 (다이나믹프로그래밍 / 동적 계획법) 파이썬

 

 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제

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

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

입력

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

출력

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

 

---

 

1. 사고하기

• 목표 : 2×n 크기의 직사각형을 채우는 방법의 수
• 유형 : DP

1x2, 2x1의 타일로 채우는 방법을 차례대로 생각해봤다. 

 

- n = 1  (1가지)

 

- n = 2 (2가지)

 

- n = 3 (3가지) :  1번개수 + 2번개수

- n = 4 (5가지) : 2번개수 + 3번개수

 

...

 

dp[1] = 1

dp[2] = 2

 

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

 

 

2. 이 문제를 공유한 이유 

 

<비슷한 문제 but 다른 점화식 유도과정>

 

나는 단순히 n이 1인 경우 2인 경우 ... 4인경우까지 해서 점화식을 유도했는데

비슷한 문제의 풀이는 약간 달라서 공유해보았다. 

 

 

이 문제에선 타일이 3개 존재한다. 

유도하는 과정은 다음과 같다. 

 

 

 

여기서 주의해야할점은 i-2까지 다 채워진 경우였다. 

1경우와 같기 때문에 빼주었는데

 

그렇게 따지면 우리 11726문제도 i-2경우에 i-1경우와 동일한 것이 존재한다.  (초록색 타일은 i-1의 경우와 같다)

 

당연히 위의 경우처럼 i-1의 경우를 고려해서 11726문제의 점화식을

a(i) = a(i-1) + a(i-2)라고 생각할 수 있다. 

 

 

 

 

---

 

정답코드

import sys
input = sys.stdin.readline

n = int(input())
dp =[0] *1001
dp[1] = 1
dp[2] = 2

for i in range(3,n+1): 
    dp[i] = (dp[i-1] + dp[i-2]) % 10007
    
print(dp[n])