[BOJ] DP 10844번 쉬운 계단 수 C++

10844번 쉬운 계단 수

📝문제링크 : www.acmicpc.net/problem/10844

 

케이스들을 조금 나열해보면, 다음을 알 수 있다.

 

계단수가 0으로 끝나려면 0의 앞자리엔 1밖에 올 수 없다. 

계단수가 9로 끝나려면 9의 앞자리엔 8밖에 올 수 없다.

계단수의 끝자리가 L = 1 ~ 8인 경우 L - 1 과 L + 1 이 모두 올 수 있다.

 

따라서 점화식은 다음과 같다.

dp[N][L] : N자리 계단수에 대해, 끝자리 수가 L인 수의 개수

 

그리고 N 자리수 계단수는, N자리 일때 끝자리 수가 0 ~ 9 인 수의 개수(dp[N][0] ~ dp[N][9]) 의 총합이다. 

 

소스코드

#include <iostream>

using namespace std;

int main()
{
    int	N;
    cin >> N;

    // dp[N][L] : N자리 계단수에 대해, 끝자리가 L인 수의 개수
    int dp[101][10];

    //set initial value
    for(int i = 0; i < 10; i++)
    {
      if (i == 0)
      	dp[1][i] = 0;
      else
      	dp[1][i] = 1;		
    }
    
    //find answer
    for(int i = 2; i <= N; i++)
    {
    	for (int j = 0; j < 10; j++)
    	{
          if (j == 0)
          	dp[i][j] = dp[i - 1][j + 1];
          else if (j == 9)
          	dp[i][j] = dp[i - 1][j - 1];
          else
          	dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
    	}
    }

    int sum = 0;
    for(int j = 0; j < 10; j++)
    	sum = (sum + dp[N][j]) % 1000000000;	
    cout << sum << '\n';
    return (0);
}

 

 

 

웹에서 수식 편집할 수 있는 사이트 찾았다.

www.sciweavers.org/free-online-latex-equation-editor

Online Latex Equation Editor - Sciweavers