[1793번] 2XN 타일링

---

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

0️⃣ 입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다.

[ 제한 ]
0 ≤ n ≤ 250

1️⃣ 출력
입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

2️⃣ 예시

---

3️⃣ 나는 어떻게 문제를 풀었을까❔

❕
대략 아이디어는 아래와 같다.

2X1로 만들 수 있는 방법의 수 + 2X2로 만들 수 있는 방법의 수 + 2X1과 2X2로 만들 수 있는 방법의 수 

근데, 이렇게 구성하고 구현을 하니까 고려해야 할 점이 너무 많았다.
2X2를 계산하기 위해서 width의 홀짝도 판별해야 하고, 2X1과 2X2로 만들 수 있는 방법도 많았다.

❕
책에서 2X1로 타일링을 했을 때 만든 점화식이 아래와 같았는데, 이 점화식과 비슷한 점화식을 만들어야 할 것 같다.

dp [n] = dp [n-1] + dp [n-2]

• dp[n-1]에서 길이 1을 추가하게 되는 경우 1x2 타일이 들어오는 방법 1가지
• dp[n-2]에서 길이 2을 추가하게 되는 경우 2x1 타일 2장과 2x2 타일 1장 들어오는 방법 총 2가지

따라서, 점화식은 아래와 같이 나올 수 있다.

dp[n] = dp[n-1] + 2*dp[n-2];

4️⃣ 코드

import java.io.*;
import java.math.BigInteger;

public class Main {

  static BigInteger[] dp;
  public static void main(String[] args) throws IOException{
    BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
    dp = new BigInteger[251];

    dp[0] =new BigInteger("1");
    dp[1] =new BigInteger("1");
    dp[2] =new BigInteger("3");

    for(int i=3; i<251; i++) {
      dp[i] = dp[i-1].add(dp[i-2].multiply(new BigInteger("2")));
    }

    String line = null;
    while((line=br.readLine())!=null) {
      int n = Integer.parseInt(line);
      System.out.println(dp[n]);
    }
    br.close();
  }
}

💟 큰 수를 저장할 수 있는 정수형은 BigInteger를 써줘야 한다.

알고리즘 분류 : 다이나믹 프로그래밍, 임의 정밀도 / 큰 수 연산