백준 C# - 10844 +)풀이

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

DP알아보러 가기

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

---

문제를 풀기 앞서 문제를 먼저 이해해보자

(문제 이해하기가 제일 어렵다..) 

 N = 자릿수

문제에서 N이 주어질때 길이가 N인 계단수라고 했는데 이 말이 무슨말인지 이해가 안갔다. 결과적으로 자릿수였다.

---

점화식 구하기

01 일단 써보자

DP문제는 점화식을 구하기 위해 일단 써보는 수 밖에 없다.

N = 1일때는 한 자릿수 숫자인 계단수를 구하고 N = 2일때는 두 자릿수 숫자인 계단수를 구해보면 아래 왼쪽 사진과 같이 나타낼 수 있다. 그리고 이를 끝 자리수 기준으로 표로 나타내면 아래 오른쪽 사진과 같이 된다.

---

02 점화식 구하기

특별히 달라지는 경우는 0과 9일때이다. 그 이외에는 그 전의 자릿수 숫자의 -1, +1의 숫자를 더해 주면 된다. 

예를 들어 끝자리수가 1인 경우 n-1의 끝자리 0과2를 더해주면 된다. 

---

03 위 아래 0을 더해준다.

위의 점화식을 사용하는 경우 0과 9일때 조건문을 추가해주어야 한다. 그러기 귀찮아서 맨 위와 맨 아래 0들을 넣은 행을 추가해주었다. 

---

04 1,000,000,000으로 나눈 나머지

모듈러 연산

DP을 사용하는 경우 중간에 값들이 매우 커질 수 있다. 그렇기 때문에 오버플로우가 발생할 수 있다. 이를 방지하고 중간 결를 제한하기 위해 모듈러 연산을 사용한다.

그렇기 때문에 오버플로우를 방지하기 위해 모듈러 연산을 사용한다.

dp[i,j] = (dp[i - 1 , j - 1] + dp[i - 1 , j + 1] )% 1000000000;

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static void Main()
        {
            int num = int.Parse(Console.ReadLine());
            long[,] dp = new long[101,12];
            for(int i = 2; i<=10;i++ )
            {
                dp[0,i] = 1;
            }

            for(int i = 1; i<num;i++)
            {
                for(int j = 1; j<=10; j++)
                {
                    dp[i,j] = (dp[i - 1 , j - 1] + dp[i - 1 , j + 1] )% 1000000000;
                }
            }
            long count = 0;
            for(int i = 1;i<=10;i++)
            {
                count += dp[num - 1, i];
            }
            Console.Write(count % 1000000000);
        }
    }
}