(10844) 쉬운 계단 수

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

단계별로 풀어보기

21단계(동적 계획법 1) 10번째

 

 

 

dp[a][b]를 마지막 자리가 b인 a자리 계단수의 개수라고 하자.

모든 한자리수는 계단수지만 처음 자리가 0인 수는 제외하므로 dp[0][0]= 0, dp[0][b]= 1(1≤b≤9)이다.

a>1이라면 dp[a][b]는 세 가지 경우로 나눠 생각할 수 있다.

1) b=0일때 계단수이려면 1에서 0으로 내려오는 경우밖에 없으므로 dp[a-1][1]과 같다.

2) b=9일때 계단수이려면 8에서 9로 올라가는 경우밖에 없으므로 dp[a-1][8]과 같다.

3) b가 1~8중 하나라면 내려올 수도 올라갈 수도 있으므로 dp[a-1][b-1]+dp[a-1][b+1]과 같다.

 

또한 제수 10억은 int의 범위(약 21억)의 절반보다 조금 작은 값이므로 오버플로우에 주의해야 한다.

예를 들어 마지막에 정답을 구할 때 dp[n][0]부터 dp[n][9]까지 다 더한 뒤 10억으로 나누는 방식으로 구현한다면 전부 더한 시점에서 이미 오버플로우가 나므로 틀린다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define p 1000000000

int main() 
{
  int n;
  
  cin >> n;
  
  vector dp(n+1, vector<int> (10));
  
  for(int i=1;i<=9;i++)  dp[1][i]= 1;
  
  for(int i=2;i<=n;i++){
    dp[i][0]= dp[i-1][1];
    for(int j=1;j<=8;j++)  dp[i][j]= (dp[i-1][j-1]+dp[i-1][j+1])%p;
    dp[i][9]= dp[i-1][8];
  }
  
  int ans= 0;
  
  for(int i=0;i<=9;i++)  ans= (ans+dp[n][i])%p;
  
  cout << ans;
  
  return 0;
}