[백준] 1793 타일링 - 동적계획법(DynamicProgramming) + 임의 정밀도 / 큰 수 연산(BigInteger) JAVA

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

코드설명

동적계획법(DynamicProgramming) + 임의 정밀도 / 큰 수 연산(BigInteger) 를 활용합니다.

 

문제에서 유의할점은, 2x2 타일링이 추가되었다는 점입니다. 이는 2x1 타일링 2개를 가로로 세워서 만든것과 동일합니다.

 

또한, 문제의 결과값이 매우 커지므로 (long형, 2^64 로도 표현이 불가) BigInteger를 활용합니다.

일반적으로는 % MOD 값을 활용해서 값이 너무 커지지 않게 처리하는데, 이번 문제에서는 큰 수 연산을 활용합니다.

자바에서는 BigInteger 클래스를 사용하고 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static BigInteger[] cache = new BigInteger[251];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		Arrays.fill(cache, BigInteger.valueOf(-1));
	    while ((line = br.readLine()) != null && !line.isEmpty()) {
			N = Integer.parseInt(line);
			System.out.println(tile(N));
		}
		
		System.out.println();
		
	}
	
	private static BigInteger tile(int n) {
		if(n == 0) return BigInteger.ONE;
		if(n == 1) return BigInteger.ONE;
		if(cache[n].compareTo(BigInteger.valueOf(-1)) != 0) return cache[n];
		BigInteger ret;
		ret = tile(n - 1).add(tile(n - 2)).add(tile(n - 2));
		return cache[n] = ret;
	}
	
}