[Java] 11726 2×n 타일링

1. 문제 📚

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

11726번: 2×n 타일링

2. 입출력 예 📋

ㅁㄴㅇㅁㄴㅇ

3. 알고리즘 ✅

1. 가짜문제 정의

dp[n] := 2*n 타일에 할 수 있는 경우의 수

2. 가장 작은 문제 해결하기 

3. 점화식 세우기

dp[n] = dp[n - 1] + dp[n - 2]

4. 소스코드 💻

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]) % 10007;
        }

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

}