쉬운계단수라는데 난 약간 어려웠다..

문제

  • 계단 수란 12321 과 같이 각 자리수의 차가 1인 수이다.
  • 숫자의 자리수가 주어졌을 때 계단 수의 갯수를 구하면 된다.

입력

  • 1보다 크거나 같고 100보다 작거나 같은 정수 N이 주어진다.

출력

  • 정답을 1,000,000,000으로 나눈 나머지를 출력하면 된다.

    예제 입력 2 예제 출력 17

접근

  • 다이나믹 프로그래밍을 어떻게 사용할까?
  • 숫자들 간에 어떤 연관이 있을까?
  • 10억은 언제 나눠줘야 할까?

내가 생각한 풀이

  • 숫자마다 다음에 올 수 있는 수는 정해져있다.
    • 1은 0과 2, 2는 1과 3, 3은 2와 4, … 9는 8
  • 따라서 그 전의 값들을 참고 하면 쉽게 찾을 수 있다!
    • 예를 들어 3으로 시작하는 4자리 수의 갯수는 3xxx와 같은 형식으로 나타나는데 xxx의 자리에 들어 갈 수 있는 수는 이미 그 전에서 구해놨다.(2로 시작하는 3자리 수와 4로 시작하는 3자리수) 따라서 그냥 두 값을 더해주기만 하면 된다!
  • 이때 9는 들어갈 수 있는 값이 8밖에 없으므로 이전 자리수의 8 값을 그대로 가져오면 되고 1은 0과 2인데 0같은 경우 30xx와 같이 나타낼 수 있으므로 전 전 자리수의 값을 더해준다.(4자리수라면 2자리수의 값)
  • 나눠주는 연산은 값을 초과하는 것을 방지하기 위하여 연산 할 때 마다 적용시켜주었다.

코드

#include<iostream>
using namespace std;
int main(void){
  int n, sum = 0;
  long long dp[101][10], r[101];
  cin>>n;
  for(int i = 1 ;i<=9;i++){
    dp[1][i] = 1;
    dp[2][i] = 2;
  }
  dp[2][9] = 1;
  r[1] = 9; r[2] = 17;
  for(int i = 3;i<=n;i++){
    for(int j = 1;j<=9;j++){
      if(j == 1){
        dp[i][j] = (dp[i-2][j] + dp[i-1][j+1])%1000000000;
      }
      else if(j==9){
        dp[i][j] = dp[i-1][j-1]%1000000000;
      }
      else{
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000;
      }
    }
  }
  for(int i = 1 ;i<=9;i++)
    sum = (sum+dp[n][i])%1000000000;
  cout<<sum;
  return 0;
}