[이코테] 바닥 공사

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 

 

2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.

 

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

 

예를 들어 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

 

입력 조건

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

 

출력 조건

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

<입력 예시>
3
<출력 예시>
5

 

---

풀이과정

이 문제 또한 이전에 개미전사

와 마찬가지로 i번째 위치에 대한 최적의 해를 구할때 왼쪽부터 (i-3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없습니다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2 x 2크기의 직사각형 형태이기 때문입니다.

 

1. 왼쪽부터 i -1 까지 길이가 덮개로 이미 채워져 있다면?

2 x 1 의 덮개를 채우는 하나의 경우밖에 존재하지 않습니다.

2. 왼쪽부터 i - 2 까지 길이가 덮개로 이미 채워져 있다면?

2 x 1 덮개를 2개를 넣는 경우 와 2 x 2 덮개를 1개 넣는 2가지 경우가 존재합니다.

 

이를 통해 우리는 점화식을 세울 수 있습니다.

 

d[i] = d[i - 1] + d[i - 2] * 2

 

# 입력 받기
n = int(input())

# 다이나믹 프로그래밍(DP)을 위한 리스트 초기화
dp = [0] * 1001

# 초기값 설정
dp[1] = 1  # 바닥 길이가 1인 경우, 1 X 2 덮개로 채울 수 있으므로 1가지 방법이 있습니다.
dp[2] = 3  # 바닥 길이가 2인 경우, 1 X 2 덮개 3개 또는 2 X 2 덮개 1개로 채울 수 있으므로 3가지 방법이 있습니다.

# DP를 이용하여 경우의 수 계산
for i in range(3, n+1):
    # 현재 바닥 길이가 i일 때, 마지막에 놓을 덮개의 종류에 따라 경우의 수를 계산합니다.
    # 1 X 2 덮개를 놓는 경우: dp[i-1]에서 바닥의 남은 길이가 1인 경우의 수를 그대로 가져옵니다.
    # 2 X 1 덮개를 놓는 경우: dp[i-2]에서 바닥의 남은 길이가 2인 경우의 수를 그대로 가져옵니다.
    # 따라서 dp[i] = dp[i-1] + 2 * dp[i-2]로 계산합니다.
    dp[i] = (dp[i-1] + 2*dp[i-2]) % 796796

# 결과 출력
print(dp[n])  # 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력합니다.