BOJ - 2×n 타일링

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

11726번: 2×n 타일링

• 다이나믹 프로그랭의 기본 예제 문제이다.
• 문제의 규칙을 보고 점화식을 만들어야한다.
• N > 3 기준으로
  • N - 2 경우의 수에서 1x2 블럭을 두개 추가하면 N의 조건을 만족하는 경우의 수가 된다.
  • N - 1 경우의 수에서 2x1 블럭을 하나 추가하면 N의 조건을 만족하는 경우의 수가 된다.
  • 고로 F(N) = F(N-1) + F(N-2) 점화식이 성립한다. (단 N > 3)

 

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


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine());

        long[] memo = new long[1001];
        memo[1] = 1;
        memo[2] = 2;

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

        System.out.println(memo[N]);
    }
}