[C++] 백준 10844번 쉬운 계단 수

 

다이나믹 프로그래밍 문제입니다.

 

숫자의 길이가 N개일 때 계단 수의 개수를 찾는 문제입니다.

계단 수는 인접한 자리수의 차이가 1이 나는것을 말합니다.

예를들어 121 1232 4343은 계단수입니다.

 

배열 memo[i][j]에 1일때의 값을 전부 넣었습니다.

i는 자리수를 의미하고 

j는 0~9까지의 숫자를 넣었을때에 대한 수를 나타냅니다.

 

0과 9의 경우 끝자리 숫자이기 때문에

0이 나오면 1이 나올 수 밖에 없고

9가 나오면 8이 나올 수 밖에 없습니다.

나머지 숫자에는 그 숫자의 +1, -1의 숫자가 나올수 있습니다.

 

if (j == 0) {
 	memo[i][j] += memo[i - 1][1] % 1000000000;
}
else if (j == 9) {
 	memo[i][j] += memo[i - 1][8] % 1000000000;
}
else {
 	memo[i][j] = (memo[i - 1][j + 1] + memo[i - 1][j - 1]) % 1000000000;
}

 

#include <iostream>
#include <algorithm>
using namespace std;

int memo[110][10];

int main(int argc, char *argv[])
{
   int n;
   int result = 0;
   cin >> n;
   memo[1][0] = 0;
   memo[1][1] = 1;
   memo[1][2] = 1;
   memo[1][3] = 1;
   memo[1][4] = 1;
   memo[1][5] = 1;
   memo[1][6] = 1;
   memo[1][7] = 1;
   memo[1][8] = 1;
   memo[1][9] = 1;

   for (int i = 2; i <= n; ++i) {
      for (int j = 0; j <= 9; ++j) {
         if (j == 0) {
            memo[i][j] += memo[i - 1][1] % 1000000000;
         }
         else if (j == 9) {
            memo[i][j] += memo[i - 1][8] % 1000000000;
         }
         else {
            memo[i][j] = (memo[i - 1][j + 1] + memo[i - 1][j - 1]) % 1000000000;
         }
      }
   }
   for (int i = 0; i <= 9; ++i) {
      result += memo[n][i];
      result %= 1000000000;
   }

   cout << result;
   return 0;
}