백준 C# - 1309 +) 풀이

 

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

DP알아보러 가기

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

---

점화식 구하기

01 일단 적어보자

N = 1,2,3이였을 경우의 수를 다 적어보자 그러면 아래와 같이 나온다.

---

02 표로 정리

표를 확인해보면 관계성을 구할 수 있으므로 아래와 같은 점화식이 나온다.

---

 

02 % 9901

모듈려 연산

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

 

---

코드 전문

using System;
namespace baek2
{

   class Program 
   {
       public static void Main()
       {
            int n = int.Parse(Console.ReadLine());
            long[,] dp = new long[100001, 4];

            if(n == 1)
            {
                Console.WriteLine(3);
                return;
            }

            dp[0, 0] = 2;
            dp[0, 1] = 2;
            dp[0, 2] = 3;
            for (int i = 1; i<=n; i++)
            {
                dp[i, 0] = (dp[i - 1, 1] + dp[i - 1, 2]) % 9901;
                dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 2]) % 9901;
                dp[i, 2] = (dp[i - 1, 0] + dp[i - 1, 1] + dp[i - 1, 2]) % 9901;
            }

            Console.Write((dp[n-2,0]+dp[n-2,1]+dp[n-2,2])% 9901);
       }
   }
}