[BOJ] 백준 1793 타일링

출처: https://www.acmicpc.net/problem/1793

 Input 
2
8
12
100
200

 Output 

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251 

2 * N 직사각형이 주어질 때, 2×1과 2×2 타일로 채우는 방법의 수

 

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

▶ DP[i] = 2 * i 직사각형에서 방법의 수

3 ≤ i 일 때, DP[i]는 DP[I-1]에서 크기  『1』만큼 늘어났기에 

□ 을 놓는 경우입니다.

① DP[i-1]에서 2*1 크기의 □을 놓는 경우입니다.

     ■ 영역은 작은 단계에서 부터 쌓여온것이기 때문에 어떤 형태든 신경쓰지 않습니다.

② DP[i-2]에서 2*2 크기의 □ 1개 or 2*1 크기의 □를 2개 놓는 경우입니다. 

    → DP[i-2] * 2 

▶ DP[i] = DP[i-1] + (DP[i-2] × 2)

※ 0 ≤ n ≤ 250이기 때문에 Java의 경우 BigInteger 이용.

※ 문제 조건상 i = 0일 때, DP[0] = 0도 정의

---

import java.io.IOException;
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
         
        // 1 ~ 250
        BigInteger[] DP = new BigInteger[250 + 1];
         
        DP[0] = new BigInteger("1"); 
        DP[1] = new BigInteger("1");
        DP[2] = new BigInteger("3");
        for(int i=3; i<=250; i++) {
            // DP[i] = (DP[i-1] + DP[i-2] * 2)
            DP[i] = DP[i-2].multiply(new BigInteger("2"));
            DP[i] = DP[i].add(DP[i-1]);
        }
         
        while(sc.hasNextInt()){
           int n = Integer.parseInt(sc.next());
           System.out.println(DP[n]);
        }
    }
}