백준 C# - 15990 +) 풀이

문제 설명

정수 N을 1,2,3 합으로 표현하는 방법의 수 

조건 : 같은 수를 연속으로 두 번 이상 사용하면 안된다.

"1 + 1 + 2" ❌
"1 + 2 + 1" ✅

---

조건이 없는 경우 (연속된 숫자가 올 수 있는 경우)

백준 C# - 9095 +)풀이

점화식

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

---

조건이 있는 경우(연속된 숫자가 올 수 없는 경우)

마지막 숫자만 확인하여 겹치게만 안하면 된다는 것이다. 다른말로  마지막 숫자만 체크하면 된다.

dp[n][1] = dp[n-1][2] + dp[n-1][3]   // 마지막이 1 → 그 전에는 2나 3
dp[n][2] = dp[n-2][1] + dp[n-2][3]   // 마지막이 2 → 그 전에는 1이나 3
dp[n][3] = dp[n-3][1] + dp[n-3][2]   // 마지막이 3 → 그 전에는 1이나 2

 

초기값

dp[1][1] = 1        // 1
dp[2][2] = 1        // 2
dp[3][1] = 1        // 2 + 1
dp[3][2] = 1        // 1 + 2
dp[3][3] = 1        // 3

---

코드 전문

using System;
using System.Text;

class Solution
{
    static void Main()
    {
        long[,] dp = new long[1000002, 4];
        int mod = 1000000009;
        dp[1, 1] = 1;
        dp[2, 2] = 1;
        dp[3, 1] = 1;
        dp[3, 2] = 1;
        dp[3, 3] = 1;

        for (int i = 4; i <= 1000001; i++)
        {
            dp[i, 1] = (dp[i - 1, 2] + dp[i - 1, 3]) % mod;
            dp[i, 2] = (dp[i - 2, 1] + dp[i - 2, 3]) % mod;
            dp[i, 3] = (dp[i - 3, 2] + dp[i - 3, 1]) % mod;
        }

        int n = int.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();

        while (n > 0)
        {
            int t = int.Parse(Console.ReadLine());
            sb.AppendLine(((dp[t, 1] + dp[t, 2] + dp[t, 3]) % mod).ToString());
            n--;
        }
        Console.Write(sb.ToString());
    }
}