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

 

 

문제 출처

백준 온라인 저지

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

문제 

 

문제 입 / 출력

 

풀이

DP를 활용해서 푼다

• 마지막 자리 수가 0로 끝나는 경우에는 맨 뒷자리 수가 1인 경우만 가능
  dp[i][j] = dp[i -1][1];
• 마지막 자리 수가 9로 끝나는 경우에는 맨 뒷자리 수가 8인 경우만 가능
  dp[i][j] = dp[i -1][8];
• 마지막 자리 수가 2 ~ 8 로 끝나는 경우에는 맨 뒷자리 수가 그 수 뒤의 앞 뒤일 경우 가능
  dp[i][j] = dp[i -1][j-1] + dp[i -1][j + 1];

 

코드

#include <iostream>

using namespace std;

int dp[101][10];
const int mod = 1000000000;

int main() {
  int n;
  long long result = 0;
  cin >> n;

  for (int i = 1; i <= 9; i++)
    dp[1][i] = 1;

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

  for (int i = 0; i <= 9; i++) {
    result += dp[n][i];
  }

  cout << result % mod << "\n";
}