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

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

10844번: 쉬운 계단 수

문제를 처음 봤을때 DFS 쓰는 문제인가? 했는데 DFS를 사용해도 답은 나오겠지만 너무 가짓수가 많아서 시간초과에 걸릴게 뻔했다.

숫자들이 규칙이 없는것이 아니라 1차이라는 규칙이 있으므로 그냥 Dp썼다.

Dp를 점점 하면서 느낀거지만 문제가 다 똑같다. 물론 아직 Dp애기 수준이라 실버1 언저리 문제만 풀지만, 현재까지 느낀바로는 그렇다.

 

문제 풀이는 각 자릿수를 정해야하는데 첫번째 자릿수에는 0이 올수 없고, 앞자릿수에 영향을 받지 않으므로 미리 세팅을 해준다.

dp[0][0]을 제외하고 나머지를 모두 1로 세팅하면 된다.(1~9까지 각각 하나씩 들어갈 수 있으므로)

두번째 부터는 0부터 9까지 다 들어갈 수 있는데, 각 숫자가 들어갈 수 있는 케이스를 더해주면 된다.

예를 들어 dp[1][0](두번째에 0이 오는 경우)는 앞선 자리가 1인 경우밖에 없으니 dp[0][1]과 똑같다.

마찬가지로 dp[1][9]는 앞선자리가 8인 경우에만 9가 올 수 있으니 dp[0][8]과 똑같다.

나머지 2~8의 숫자는 앞선 자리의 숫자가 해당 숫자에 각각 1씩 더하고 뺀 숫자들로 만들어질 수 있으므로 각각의 두 경우를 모두 더해주면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define Mod 1000000000;

using namespace std;
int main(){
  ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int n; cin >> n;
  int **dp = new int*[n];
  for(int i = 0; i<n+1; i++){
    dp[i] = new int[10];
  }
  for(int i = 0; i<n; i++){
    for (int j = 0; j<10; j++){
      dp[i][j] = 0;
    }
  }

  for(int i = 1; i<10; i++){
    dp[0][i] = 1;
  }
  for(int i = 1; i < n; i++){
    for(int j = 0; j < 10; 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;
    }
  }
  int sum = 0;
  for(int i = 0; i<10; i++){
    sum = (sum + dp[n-1][i]) % Mod;
  }
  cout << sum;
}

 

 

 

 

 

보다시피 한번 틀렸는데 마지막 sum을 구할때 다 구하고 10억을 mod 연산을 해주었는데, 그렇게 하면 도중에 숫자가 너무 커져서 overflow로 숫자가 달라지는 것 같다.

그래서 for문을 돌릴때마다 mod연산을 해주었더니 바로 통과되었다.