[백준] 2133번: 타일 채우기 [C#]

 

점화식: dp[N] = dp[N-2] * 3 + ∑(dp[i] * 2) (i 는 0이 될때까지 2씩 감소)

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _2133_boj
    {
        public void boj_2133()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[] dp = Enumerable.Repeat(0, 31).ToArray();
            dp[0] = 1;
            dp[2] = 3;
 
            for (int a = 4; a <= N; a += 2)
            {
                dp[a] = dp[a - 2] * 3;
                for (int i = a - 2; i >= 2; i -= 2)
                {
                    dp[a] += dp[i - 2] * 2;
                }
            }
 
            Console.WriteLine(dp[N]);
        }
    }
}