Search

바닥 공사

문제 : 바닥 공사

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

문제

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

입력 조건

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

출력 조건

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

입력 예시

3
Python

출력 예시

5
Python

풀이

해결에 필요한 핵심 아이디어: 보텀업 DP

답안

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.