10844 : 쉬운 계단 수 (Dynamic Programming) [C,C++]

1자리 경우의 수는 - 9개, 2자리 경우의 수는 -17개, 3자리 경우의 수는? 

값이 1부터 100까지의 입력을 받으므로 쉬운 계단 수 문제 역시 DP 문제의 핵심인 각 단계의 서로 간 연관성을 알아내는 것이 중요하다.

당연한 얘기지만 한 칸 마다 값 차이가 1씩 나는 것을 이용해야 한다. 

간단히 생각해보자. 2자리의 경우의 수를 나열해보면,

0으로 끝나는 수는 10이 있다.

1로 끝나는 수는 21이 있다.

2로 끝나는 수는 12, 32가 있다.

3으로 끝나는 수는 23, 43이 있다.

4로 끝나는 수는 34, 54가 있다.

5로 끝나는 수는 45, 65가 있다.

6으로 끝나는 수는 56, 76이 있다.

7로 끝나는 수는 67, 87이 있다.

8로 끝나는 수는 78, 98이 있다.

9로 끝나는 수는 89가 있다.

여기서 규칙 3가지를 도출할 수 있는데,

규칙 1) 0으로 끝나는 수는 그 전의 자릿 수가 1로 끝나는 수이다.

규칙 2) 9로 끝나는 수는 그 전의 자릿 수가 8로 끝나는 수이다.

규칙 3) 나머지 수는 그 전의 자릿 수가 현재 숫자의 (-1, +1)로 끝나는 수이다.

이 규칙을 코드로 쓴다면,

for (int i = 1; i < this->HowManyStairs; i++)
{
        Sum = 0;
 for (int j = 0; j < 10; j++)
 {
  if(j == 0)
   this->Space[i][0] = this->Space[i - 1][1];
  else if(j == 9)
   this->Space[i][9] = this->Space[i - 1][8];
  else
   this->Space[i][j] = (this->Space[i - 1][j - 1] + this->Space[i - 1][j + 1]);
  
  Sum += this->Space[i][j];
 }
}

<pseudo code>

*Source of the problem = https://www.acmicpc.net/problem/1005

*문제 출처 : BAEKJOON ONLINE JUDGE