백준 C# - 2193 +) 풀이

 

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

DP알아보러 가기

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

---

점화식 찾기

01 일단 적어보기

DP문제는 점화식을 구해야 하는데 일단 적어보고 어떤식으로 반복되는지 찾아야한다.

 

 

 

02 점화식 찾기

위의 적어 놓은 것을 표로 정리하면 아래와 같다.

각각의 0과 1이 어떻게 나오는지 살펴보면 0의 갯수는 앞의 0과 1의 갯수의 합이고 1의 갯수는 앞의 0의 갯수임을 알 수 있다.

그러므로 점화식은 아래와 같이 표시할 수 있다.

---

주의!

int형을 쓰면 안된다

90자리 이친수의 개수  2,880,067,194,370,816,120 이다.

int(4byte 2³²)가 나타낼 수 있는 값의 범위는 - 2,147,483,647 ~  2,147,483,648으로 int를 사용하게 되면 값의 범위가 넘어가게 된다 그러므로 long을 사용해야 한다.

long(8byte 2⁶⁴)이 나타낼 수 있는 값의 범위는 9,223,372,036,854,775,807이므로 값의 범위에 해당된다.

---

코드 전문

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

            for(int i = 1; i<=num;i++)
            {
                dp[0,i] = dp[0,i - 1] + dp[1,i - 1];
                dp[1,i] = dp[0,i - 1];
            }
            Console.Write(dp[0,num-1] + dp[1,num-1]);
        }
    }
}