바닥 공사

💻 입력 조건

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

💻 출력 조건

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

💻 입력 예시
3

💻 출력 예시

5

📖 문제 해결
다이나믹 프로그래밍을 이용하여 왼쪽부터 차례대로 바닥을 채워나간다고 생각하며 알고리즘을 작성해나가보면 해결할 수 있는 문제입니다.

2 x 1 크기의 바닥을 채우는 경우의 수와 2 x 2 크기의 바닥을 채우는 경우의 수는 쉽게 구할 수 있으니 미리 설정해 줍니다.

그리고 점화식의 개념을 이용하여, 2 x N-2 크기의 바닥을 채우는 경우의 수와 2 x N-1 크기의 바닥을 채우는 경우의 수를 알면 쉽게 2 X N 크기의 바닥을 채우는 경우의 수를 구할 수 있습니다.

• 우선 2 X N 크기의 바닥 중 2 x N-1 크기만큼 바닥을 채운 후에 나머지 1 만큼의 크기의 바닥을 채우는 경우에는 1가지 경우의 수가 있으므로, 이 경우 수는 2 x N-1 크기의 바닥을 채우는 경우의 수와 같습니다.
• 그리고 2 X N 크기의 바닥 중 2 x N-2 크기만큼 바닥을 채운 후에 나머지 2 만큼의 크기의 바닥을 채우는 경우에는 2가지 경우의 수가 있으므로, 이 경우 수는 2 x N-2 크기의 바닥을 채우는 경우의 수의 2배가 됩니다.
• 따라서 2 X N 크기의 바닥을 채우는 전체 경우의 수 = 2 x N-1 크기의 바닥을 채우는 경우의 수 + (2 x N-2 크기의 바닥을 채우는 경우의 수) * 2 가 됩니다.

이를 다이나믹 프로그래밍(보텀업 방식)으로 구현하면 코드는 다음과 같습니다.

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

# 메모를 위한 리스트 d 설정
d = [0] * (n+1)

# d[1], d[2] 값 설정
d[1] = 1
d[2] = 3

# d[3]부터 d[n]까지 점화식을 이용하여
# 차례대로 값을 계산
for i in range(3,n+1):
    d[i] = d[i-1] + 2*d[i-2]
    
# d[n] 값 출력
d[n]