[JAVA]백준_11727_2*N 타일링2

문제링크

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

11727번: 2×n 타일링 2

 

 

 

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		BigInteger d[] = new BigInteger[N+1];
		if(N>=1) d[1] = new BigInteger("1");
		if(N>=2) d[2] = new BigInteger("3");

		for(int i=3;i<=N;i++) {
			d[i] = d[i-1].add(d[i-2]).add(d[i-2]);
		}
		
		System.out.println(d[N].remainder(new BigInteger("10007")));
	}
}

 

직사각형이 있을 때

1*2  짜리 타일을 쓰고 남은 공간 채우는 법

2*1 짜리 타일을 쓰고 남은 공간 채우는 법

2*2 짜리 타일을 쓰고 남은 공간 채우는 법

을 구하면

d[i] = d[i-1] + d[i-2] + d[i-2] ;

이다

숫자가 크게 넘어가는 것 같아서 BigInteger를 사용해서 해결해보았다.