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

2 x N 은 2 x (N-1)과 2 x (N-2)의 합으로 이루어진다.

2 x (N-2)에서 2x1 블록으로 채운경우는 2 x (N-1)에 1x2 하나로 채운경우에 포함된다.

C++ 코드(bottom-top)

#include <iostream>

using namespace std;

long long arr[1000] = { 0,1,2 };

int main() {
	int n = 0;
	scanf("%d", &n);

	for (int i = 3; i <= n; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
		
	}
	printf("%d", arr[n]);
}

C# 코드

using System.Text;
using System;
using static System.Console;

class Program
{
    static long[] arr = new long[1001];
    public static void Main(string[] args)
    {
        arr[0] = 0; arr[1] = 1; arr[2] = 2;

        int n = int.Parse(ReadLine());
        for( int i = 3; i<=n; i++)
        {
            arr[i] = (arr[i - 1] + arr[i - 2])%10007;
        }
        Write(arr[n]);

    }
}

Java 코드

import java.util.*;

public class Main {
    static long[] arr = new long[1001];

    public static void main(String[] args) {
        arr[0] = 0; arr[1] = 1; arr[2] = 2;
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();

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

    }
}

Kotlin 코드

import java.util.*
import kotlin.math.*

fun main(args: Array<String>){
    val arr = LongArray(1001)
    arr[0] = 0; arr[1] = 1; arr[2] = 2;
    val s = Scanner(System.`in`)
    val n = s.nextInt()

    for(i in 3..n){
        arr[i] = (arr[i-1] + arr[i-2])%10007
    }
    println(arr[n])

}

Python 코드

arr = [0 for _ in range(1001)]
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
n = int(input())
for i in range(3, n+1):
    arr[i] = (arr[i-1] + arr[i-2])%10007
print(arr[n])