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

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

11726번: 2×n 타일링

 

---

• 문제
• 소요시간: 13분 22초

---

• 설계하기(접근방법) 

1. n을 입력받는다

2. 알고리즘 해석

1) n = 1일 때

1 개

2) n = 2일 때

가로로 놓는 방법과 세로로 놓는 방법 -> 2가지

3) n = 3일 때

세로로 3 -> 1가지

(가로 2 세로 1) *  2 -> 2가지

총 : 3가지

4) n = 4일 때

가로 4 -> 1가지

세로 4 -> 1가지

가로 2 세로 2 -> 3가지

총 : 5가지

 

세로 직사각형을 세우는 경우는 가로 1칸을 차지한다

하지만 가로 직사각형을 세우는 경우는 2칸을 차지하고 두 쌍을 항상 함께 가져간다

 

동적 프로그래밍을 떠올리면

dp[5] = dp[4] 에다가 세로 직사각형을 세운 경우와

dp[5] = dp[3] 에다가 가로 직가각형 2개를 추가한 경우 2가지가 나온다 

 

이를 점화식으로 표현하면

 

dp[n] = dp[n-1] + dp[n-2]이다

 

이를 반복문의 형태로 구현하여 dp[n]의 값을 구한다

 

3. 10007로 나눈 나머지를 출력한다.

---

• 코드(출력)

n = int(input())

dp = [0] * (n + 1)

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

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

print(dp[n]%10007)

---

• 얻어갈 부분

1. 동적 프로그래밍인 것을 알고 풀면 쉽지만, 모르고 풀었을 때는 어려울 수 있다. 그리기, 동적 프로그래밍 등 어떤 유형으로 접근해야 하는지 시각을 길러야 할 것이다.