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

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

---

● 문제

n의 입력에 따라 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 계산하는 dp 문제이다.

n=1부터 각각 하나씩 그림을 그려보면서 수를 세어보게되면

n	1	2	3	4	5	6	7	8	9
경우의 수	1	2	3	5	8	13	21	34	55

즉, dp[n] = dp[n - 2] + dp[n - 1]의 경우의 수가 발생하게 된다.

 

근데 문제에서 10007로 나눈 나머지를 출력하라고 하여서 결과값 출력때 10007을 나누게 되면 Integer.MAX_VALUE를 넘어 Overflow가 발생하므로 연산시에 10007로 나눈 나머지를 저장해주어야한다.

---

● 코드

import java.io.*;

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());
        int[] dp = new int[1001];

        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
        }

        System.out.println(dp[n]);

    }


}