[BOJ] 11726 2xn 타일링 - JAVA

1. 문제

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

---

2. 풀이

규칙

• 결론부터 얘기하면 피보나치다.
• N을 N-1, N-2부분으로 나눠서 생각하면 쉽다. 항상 앞에 1칸 세로 또는 2칸 가로가 붙는다고 생각하면 된다. 

코드

• dp배열 크기를 가변적으로(N+1)정해줬으므로 N<3인 경우는 인덱스 에러를 방지하기 위해 따로 경우를 뼀다.
• 그 외는 123더하기 문제와 비슷하다.

public static void main(String[] args) throws IOException {
   int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
   int[] dp = new int[N+1];
   int DIV = 10007;

   if(N<3){
      System.out.println(N);
      return;
   }

   dp[1] = 1;
   dp[2] = 2;
   for(int i=3;i<=N;i++) dp[i] = (dp[i-1]+dp[i-2])%DIV;

   System.out.println(dp[N]);
}

---

3. 결과