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

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

11726번: 2×n 타일링

 

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

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-1]+dp[i-2];
            dp[i]%=10007;
        }

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

 

n = 4일 때까지 그림을 그려보니,

 

dp[i] = dp[i-1]+dp[n-2] 의 점화식이 도출됐다.

 

dp[n-1] 사각형에 세로 직사각형 하나가 추가되고, dp[n-2] 사각형에 가로 직사각형 두개가 추가되는 것이 반복적으로 이루어진다. 

 

이 때, 10007을 마지막에 한번 나눠줘서 틀렸는데 그러면 Integer.MAX_VALUE를 넘어 오버플로우가 발생할 수 있어 dp[i]를 구할때 매번 나눠줘야 한다.