[DP] 바닥 공사

문제

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

 

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

 

입력 조건

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

출력 조건

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

입력 예시

3

 

출력 예시

5

---

아이디어

대표적인 DP 알고리즘 문제이다. 그림을 그려서 풀어보면 해결할 수 있다.

위 그림과 같이 2 x N 바닥을 타일로 채우는 경우는 [i - 1에서 2 x 1 타일 하나 / i - 2에서 2 x 2 타일, 1 x 2 타일 2개] 가 추가된다. 이를 점화식으로 세우면

• a_i = a_i-1 + a_i-2 x 2

이를 Bottom Up 방식으로 해결하면 된다.

---

코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());

int[] dp = new int[1001];

dp[1] = 1;
dp[2] = 3;
for(int i=3; i<=N; i++) {
    dp[i] = (dp[i-1] + 2*dp[i-2]) % 796796;
}
System.out.println(dp[N]);