[BOJ/백준] 11726 2×n 타일링 (S3)

문제

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

풀이

규칙만 찾아면 피보나치 수열인 것을 알 수 있다.

Code

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        bw.write(fibonacci(n) + "");
        bw.flush();
        bw.close();
    }

    public static int fibonacci(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        int dp[] = new int[n + 1];
        dp[1] = 1;  // 초기값
        dp[2] = 2;  // 초기값
        for (int i = 3; i <= n; i++) {  // 나머지는 일반적인 피보나치 수열과 동일
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }

        return dp[n];
    }
}