[알고리즘/동적 계획법] 11727 번 : 2 × n 타일링 2 - python

링크 : https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

---

• 문제
• 소요시간: 15분 20초

 

---

• 설계하기(접근방법) 

1. n을 입력받는다

 

2.알고리즘 해석

칸을 채우는 경우는 다음의 경우의 수로 나뉜다.

 

1) 1* 2 세로 직사각형을 세우는 경우 : 한 칸

 

2) 2*1 가로 직사각형을 세우는 경우 : 두 칸 , 항상 두 직사각형이 같이 가야 한다.

 

3) 2*2 정사각형을 세우는 경우 :  두 칸

 

경우의 수

 

dp[1] = 1

세로 1개

 

dp[2] = 3

가로 두개, 세로 두 개, 정사각형 1 개

 

dp[3] = 5

가로 두개 + 세로 1개 * 2 - 2가지

세로 3개 * 1 - 1가지

정사각형 1개 + 세로 1개 * 2 - 2가지

 

dp [3] = dp[1] * 2 + dp[2] 인 것을 알 수 있다

 

그 이유는 

dp[1]에 정사각형 혹은 가로 두 개를 추가한 것이 dp[3]이 되고

dp[2]에 세로 직사각형 한 개를 추가한 것이 dp[3]이 된다

 

따라서 점화식은

dp[n] = dp[n-1] + dp[n-2] × 2임을 알 수 있다

 

3. dp[n] % 10007을 출력한다.

 

 

 

---

• 코드(출력)

n = int(input())

dp = [0] * (n + 2)

dp[1] = 1
dp[2] = 3

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

print(dp[n]%10007)

 

---

• 얻어갈 부분

1. 이전 유형의 문제와 유사한 문제여서 쉽게 풀었다.

2.