백준C# - 11727 +) 풀이

이 문제를 풀기 앞서 아래 문제를 먼저 풀고 오는 것을 추천한다.

백준 C# - 11726

백준 C# - 11726 +) 풀이

---

11726을 풀고 나서 아래의 점화식을 얻었다.

 

2x2와 관련된 부분만 추가해주면 된다. (자세한 설명은 11726페이지 참조)

01 2x2

끝에 부분이 2x2인 경우의 수는 dp[i-2]와 같으므로 원래 있던 점화식에 이 부분만 추가해 주면 된다.

 

 

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[] dp = new int[n + 1];

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

            for(int i = 2; i<n;i++)
            {
                dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;              
            }
            Console.Write(dp[n-1]);
        }
    }
}