백준 11726번 : 2xn 타일링

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

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

public class Main {
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+2];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

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

    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

dp를 활용한다.

주어진 타일 두 번째 항을 i에서 빼준다.

dp[i] = dp[i-2] + dp[i-1]이라는 점화식이 성립한다.

dp[i]의 값이 오버플로우가 될 수 있기 때문에 문제 설명처럼 10007을 나눈 나머지를 dp에 저장하고

원하는 정수의 값을 출력한다.