[백준] 11726번 2xn 타일링 (Python, DP)

<문제 링크>

[백준 11726번 2xn 타일링](https://www.acmicpc.net/problem/11726

---

문제 요약

2xn 크기의 직사각형을 1x2, 2x1 크기의 타일로 채울 수 있는 경우의 수를 구하는 문제이다. 출력할 때 경우의 수를 그대로 출력하면 안되고 10007로 나눈 나머지를 출력해야 한다.

ex0)

• 입력 : 2
• 채울 수 있는 경우 : ll, =
  (2x1 두개로 채우기, 1x2 두개로 채우기)
• 출력 : 2

---

문제 풀이

이 문제는 DP 문제 답게 n을 1부터 키워가며 규칙을 찾은 후, 점화식을 세워 해결해야 하는 문제이다.

(n = 6) 까지 타일을 채워보자

n	경우들	경우의 수
1	l	1
2	ll, =	2
3	lll, l=, =l	3
4	llll, ll=, l=l, =ll, ==	5
5	lllll, lll=, ll=l, l=ll, =lll, l==, =l=, ==l	8
6	llllll, llll=, lll=l, ll=ll, l=lll, =llll, ll==, l==l, ==l, l=l=, =l=l, =ll=, ===	13
...	...	...

위 표를 보면 (n = 1 ~ 6) 까지 다음과 같이 증가한다.
-> 1, 2, 3, 5, 8, 13, ...

=> 앞에 두 수를 합한 값이 자기 자신이 되는 것을 확인할 수 있다.

따라서 (n = x) 일 때 해당 문제의 출력 값을 T(x) 라 하면,
점화식을 다음과 같이 나타낼 수 있다.

T(x) = T(x-1) + T(x-2)

---

구현

사실 점화식을 구하고 나면 구현은 세상에서 제일 쉽다.

n = int(input())
ansList = [0]*n
ansList[0] = 1

if n >= 2:
    ansList[1] = 2
    for i in range(2, n):
        ansList[i] = ansList[i-1] + ansList[i-2]

print(ansList[n-1] % 10007)

처음 제출할 때 10007로 나눈 나머지를 까먹어서 시작과 동시에 틀렸다고 나와 당황했었다. 문제 조건을 까먹으면 안된다.

DP는 많이 많이 풀어보는게 제일 좋은 것 같다. 더 풀어보자.