[백준] 11727번 2*n 타일링 2

문제 및 입출력

문제 접근

문제를 보자마자 Dynamic Programming 방법을 떠올렸다.

2*3을 예시로 생각하면,
1*2를 먼저 넣을 경우와 나머지 경우로 분리했다.

1*2를 먼저 넣은 경우, 나머지 2칸은 2*1과 2*2 두 가지 경우이다.
그리고 2*1을 먼저 넣은 경우, 나머지 1칸은 1*2를 넣은 경우이다.
다음 2*2를 먼저 넣은 경우, 나머지 1칸은 1*2를 넣은 경우이다.

구현 코드

import java.io.*;

public class Main {
  static int dp[];

  static int cal(int a) {
    if(a == 0 || a == 1) {
      return 1;
    }
    if(dp[a] > 0) {
      return dp[a];
    } else {
      dp[a] = cal(a-1) + 2 * cal(a-2);
      return dp[a] %= 10007;
    }
  }

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

    System.out.println(cal(n));
  }
}