백준 C# - 15988 +) 풀이

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

백준 C# - 9095

백준 C# - 9095 +)풀이

---

점화식 부분은 9095와 동일하다.

01 케이스 T

다른 부분이 있다면 케이스 T가 추가되었다. 

while (T > 0)
{
    int N = int.Parse(Console.ReadLine());
    Console.WriteLine(dp[N-1] % 1000000009);
    T--;
}

 

---

02 % 1000000009

모듈려 연산

C# - 모듈러 연산(나머지 분배 법칙)

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static void Main()
        {
            int T = int.Parse(Console.ReadLine());
            long[] dp = new long[1000001];
            dp[0] = 1;
            dp[1] = 2;
            dp[2] = 4;
            for (int i = 3; i < 1000001; i++)
            {
                dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
            }
            while (T > 0)
            {
                int N = int.Parse(Console.ReadLine());
                Console.WriteLine(dp[N-1] % 1000000009);
                T--;
            }
        }
    }
}