백준알고리즘 1793번 타일링

백준알고리즘

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

문제를 보면 예제에 결과값의 수를 보자. Int, Long의 범위형을 초과할 수 있음을 알 수 있다. 이번 문제는 BigInteger을 사용해야 풀 수 있다. 공식은 D[i] = D[i-2] * 2 + D[i-1] 이다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger[] memoArray = null;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        memoArray = new BigInteger[251];
        memoArray[0] = BigInteger.valueOf(1);
        memoArray[1] = BigInteger.valueOf(1);
        while(scan.hasNextInt()) {
            int inputData = Integer.parseInt(scan.nextLine().trim());
            
            for(int i=0; i <= inputData; i++) {
                if(memoArray[i] != null) {
                    continue ;
                }
                
                BigInteger mul = memoArray[i-2].multiply(BigInteger.valueOf(2));
                BigInteger data = memoArray[i-1];
                memoArray[i] = data.add(mul);
            }
            
            System.out.println(memoArray[inputData]);
        }
    }
}