[Algorithm] 바닥 공사

문제

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

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

바닥

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

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

 

입력 조건

첫째 줄에 N이 주어진다.

 

출력 조건

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

 

풀이

N = 1일 때, 2 X 1 1가지

N = 2일 때, (2 X 1) X 2, (1 X 2) X 2, (2 X 2) 3가지

N = 3일 때, (2 X 1) + (2 X 2), (2 X 2) + (2 X 1), (2 X 1) X 3, (2 X 1) + 2(1 X 2), 2(1 X 2) + (2 X 1)

 -> 타일이 놓여지는 순서가 바뀌어도 다른 경우의 수임.

 -> N=2일 때 경우의 수 + N=1일 때 경우의 수 * 2

 

N = i 일 때, i - 1까지 타일이 채워져 있다면, (2 X 1) 타일로 채우는 1가지 경우만 존재함.

i - 2까지 타일이 채워져 있다면, (2 X 2) 타일을 놓거나, (1 X 2) 타일 2개를 놓는 2가지 경우만 존재함.

 (2 X 1) 타일 2개 놓는 경우를 생각할 수 있지만, i-1까지 채워진 경우에서 이미 판단됨.

 

점화식으로 정리하자면,

Ai = A(i-1) + A(i-2) + A(i-2) = A(i-1) + 2A(i-2)로 정리할 수 있다.

 

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    int[] d = new int[1001];

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.close();

    d[1] = 1;
    d[2] = 3;
    for (int i = 3; i <= n; i++) {
      d[i] = (d[i-1] + (d[i-2] * 2)) % 796796;
    }

    System.out.println(d[n]);

  } // end main
}