[Python][이코테] 바닥 공사 / DP

바닥 공사

문제

문제가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.

태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력한다. 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

입력 예시

3

출력 예시

5

---

앞서 개미 전사 문제를 풀어보고 유사하게 DP 테이블을 이용하여 풀어보고자 하였다.

 

우선 2 x 1 크기의 타일은 무조건 1가지 경우의 수뿐이다.

 

 

2 x 2 일 때는 

 

3가지 방법이 존재하게 된다.

 

즉

 

dp[1] = 1

dp[2] = 3

의 초기 규칙을 얻을 수 있다.

 

이후 2 x 3의 경우를 보면

 

5가지 경우의 수를 얻을 수 있다.

 

이제 규칙을 찾아보자면

위와 같이 맨 위의 i-1일 때 흰 칸들

 

i-2 일때 흰 칸들을 우리는 이미 알고 있다는 것이다.

 

dp table

1

3

5

일 때

 

n 이 4일 경우

위와 같은 경우의 수를 얻을 수 있는데

 

맨 위의 흰 3칸의 경우의 수는 dp[i - 1]인

그다음

 

아래 두 칸의 경우는

1

3

5

dp[i - 2]에 해당하는 값이 된다.

 

그리고 dp[i - 2] 의 경우에는 1 x 2 블럭과 2 x 2블럭 두가지 경우의 수가 존재하기 때문에

 

dp[i - 2] x 2를 해준 값을 앞의 dp[i - 1]의 값과 더해준 것이 n = 4일 때 경우의 수가 된다.

 

즉 

 

dp[4] = dp[i - 1] + (dp[i - 2] x 2)

         = 5 + 2 x 3 = 11

---

# 8-7 DP 바닥 공사
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])