[백준 11726번] 2xn 타일링 - JAVA

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

11726번: 2×n 타일링

풀이

사용한 알고리즘 : 다이나믹 프로그래밍(DP)

 

풀이전략

d[i] 는 2xi 직사각형을 2x1, 1x2 타일로 채우는 방법의 수를 담은 변수이다.

 

2x1 타일은 d[i-1] 에 하나의 타일을 덧붙인 것과 같은 결과이고,

1x2 타일은 d[i-2] 에 두개의 타일을 덧붙인 것과 같은 결과이다.

 

따라서 d[i] = d[i-1]+d[i-2]라는 식이 도출된다.

 

만약 2x2 타일도 존재했다면, d[i-2]에서 덧붙일 수 있느 경우의 수가 하나에서 두개가 되는 것이므로

d[i] = d[i-1]+d[i-2] *2 가 되었을 것이다.

 

이 문제를 풀이할 때 주의할 점은,

4byte의 int나 8byte의 long 타입을 사용하면 overflow가 발생하기 때문에

BigInteger를 사용해야 한다는 것이다. 

 

BigInteger 사용법은 아래와 같으니 참고하자.

BigInteger bigNumber1 = new BigInteger("100000");
BigInteger bigNumber2 = new BigInteger("10000");
		
System.out.println("덧셈(+) :" +bigNumber1.add(bigNumber2));
System.out.println("뺄셈(-) :" +bigNumber1.subtract(bigNumber2));
System.out.println("곱셈(*) :" +bigNumber1.multiply(bigNumber2));
System.out.println("나눗셈(/) :" +bigNumber1.divide(bigNumber2));
System.out.println("나머지(%) :" +bigNumber1.remainder(bigNumber2));

//BigInteger 형 변환
BigInteger bigNumber = BigInteger.valueOf(100000); //int -> BigIntger

int int_bigNum = bigNumber.intValue(); //BigIntger -> int
long long_bigNum = bigNumber.longValue(); //BigIntger -> long
float float_bigNum = bigNumber.floatValue(); //BigIntger -> float
double double_bigNum = bigNumber.doubleValue(); //BigIntger -> double
String String_bigNum = bigNumber.toString(); //BigIntger -> String

//두 수 비교 compareTo 맞으면 0   틀리면 -1
int compare = bigNumber1.compareTo(bigNumber2);
System.out.println(compare);

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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