백준 11727번 (11726 심화 버전)

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

import java.util.*;

import static java.util.Collections.*;

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());

    long[] dp = new long[N+3];


    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;

    for (int i = 1 ; i <N;i++)
    {
        dp[i+2] = (dp[i+1]+dp[i]*2) % 10007;
    }



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

// 11 --
// 111 1-- --1
// 1111 ---- 11-- --11 1--1
// 11111 1---- ----1 1--11 11--1 111-- --1-- --111
// 111111

    // 새로운 식 정립
    // 111 1-- --1 ㅁ1 1ㅁ
    // 1111 11-- --11 1--1 ---- ㅁㅁ ㅁ-- --ㅁ 1ㅁ1 11ㅁ ㅁ11
    // 11111 1---- ----1 1--11 11--1 111-- --1-- --111 ㅁ111 ㅁㅁ1 ㅁ--1 ㅁ1-- 1ㅁ11 1ㅁ-- 11ㅁ1 --ㅁ1






}

}

진짜로 점화식 구하려고 노력했는데 너무 어려웠다. 이번 문제는 지피티를 이용해서 점화식을 구했다. 
생각보다 너무 빡센 점화식이여서 놀랐다.