백준 C# - 11057

DP를 이용해서 풀어야한다.

DP알아보러 가기

C# - 다이나믹 프로그래밍(DP)

---

점화식 구하기

이번 문제는 점화식을 쉽게 구할 수 있다. 한번 1일 경우와 2일경우를 쭉 쓰다보면 0에서는 1-9까지 1에서는 2-8까지 이런식으로 더해지는 것을 확인할 수있다. 그래서 아래와 같이 점화식을 구해서 제출했는데 바로 통과했다!

dp[i, 0] = (dp[i - 1, 0] + dp[i-1, 1]+ dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9])% 10007;
dp[i, 1] = (dp[i - 1, 1] + dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 2] = (dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 3] = (dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 4] = (dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 5] = (dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 6] = (dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 7] = (dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 8] = (dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
dp[i, 9] = dp[i - 1, 9] % 10007;

---

코드 전문

using System;
namespace baek2
{

   class Program 
   {
       public static void Main()
       {
            int n = int.Parse(Console.ReadLine());
            long[,] dp = new long[1001, 11];
            for(int i = 0; i<10;i++)
            {
                dp[0, i] = 1;
            }

            for(int i = 1; i<n;i++)
            {
                dp[i, 0] = (dp[i - 1, 0] + dp[i-1, 1]+ dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9])% 10007;
                dp[i, 1] = (dp[i - 1, 1] + dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 2] = (dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 3] = (dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 4] = (dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 5] = (dp[i - 1, 5] + dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 6] = (dp[i - 1, 6] + dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 7] = (dp[i - 1, 7] + dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 8] = (dp[i - 1, 8] + dp[i - 1, 9]) % 10007;
                dp[i, 9] = dp[i - 1, 9] % 10007;
            }
            long answer = 0;
            for(int i = 0; i<10;i++)
            {
                answer += dp[n - 1, i];
                
            }
            Console.Write(answer % 10007);
       }
   }
}