[동적계획법] 난이도1.5, 이취코 223p '바닥 공사' (Python)

<문제>

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다.

<입력 조건>

• 첫째 줄에 N이 주어진다. (1<=N<=1,000)

<출력 조건>

• 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

---

<문제 풀이>

1. N==1일 때, 경우의 수는 1이다.

2. N==2일 때, 경우의 수는 3이다.

3. N==3일 때, 경우의 수는 5이므로, (d[N-1]+2) * (N-2)라는 공식이 성립된다. 왜냐하면 가로의 길이가 1만큼 늘어났을 때 기존 있던 경우에서 2개 더 만들 수 있고, 2만큼 늘어나면 2배 더 만들 수 있기 때문이다.

 

<코드>

n = int(input())

d = [0] * 1001

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

print(d[n])

 

<고쳐야 할 점>

• 동적계획법 문제라는 거 파악하기
• 최소 2개의 모든 경우의 수를 구하고 그걸 응용하기
• 복습 알고리즘