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

타일링1 문제에서 한가지의 경우만 더 추가된 경우이고,

점화식은 d[n] = d[n-1] +d[n-2] + d[n-2]

C++ 코드(bottom-top)

#include <iostream>
using namespace std;

int d[1001] = { 0,1,3 };

int main() {
	int n; 
	cin >> n;

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

	cout << d[n];

}

c# 부터 갯수에만 집착한 코드…ㅜ

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] = 3;

        int n = int.Parse(ReadLine());
        for( int i = 3; i<=n; i++)
        {
            arr[i] = arr[i - 1] * 2;
            if (i % 2 == 0) arr[i] += 1;
            else arr[i] -= 1;
            arr[i] = arr[i] %= 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] = 3;
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();

        for(int i = 3; i<=n; i++){
            arr[i] = arr[i-1]  *2;
            if(i % 2 == 0) arr[i] += 1;
            else arr[i] -=1;
            arr[i]%= 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] = 3;
    val s = Scanner(System.`in`)
    val n = s.nextInt()

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

}

Python 코드

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