백준 1562 계단 수 C++

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

1562번: 계단 수

개인적으로 아이디어를 떠올리기가 조금 까다로운 문제였습니다. dp를 어떻게 효율적으로 할 지 까다로웠지만 제가 사용한 방법은 다음과 같습니다.

 

dp[ i ][ j ][ k ] = i번째에 j라는 수가 들어갔고 이 때 k만큼 체크된 상황

이라고 할 때 (1번째는 왼쪽을 기준입니다.) (체크는 비트스트링을 이용합니다.)

 

dp[ i ][ j ][ k | (1 << j) ] += dp[ i - 1 ][ j - 1 ][ k ] + dp[ i - 1][ j + 1][ k ] 입니다.

왜냐하면, i번째에 새롭게 j 라는 수가 들어올 때 새롭게 체크되는 상황은 k | (1 << j) 이고,

이 케이스는 이전 경우인 i - 1번째에 j - 1, j + 1이라는 수가 사용되어야 계단 수이고, 이 때 k 만큼 체크되었었습니다.

그러므로 현재 케이스 (dp[ i ][ j ][ k | (1 << j) ]) 와 합을 구해주면 됩니다.

 

단, j = 0, 9 일 때는 i - 1번째 수가 1, 8 밖에 없으므로 주의하여 dp를 계산하면 됩니다.

그리고 첫 번째 수가 0이 될 수는 없으므로, 첫 번째 수가 1 ~ 9일 때 dp를 1로 초기화합니다.

 

마지막으로 dp[ n ][ j ][ 1023 ] 을 보면, n번째 수가 j 인데 체크가 1023 = 1111111111 만큼 진행된 경우이므로, j가 0 ~ 9까지인 경우를 모두 더하면, n자리 계단 수이면서, 0 ~ 9를 모두 사용한 경우입니다.

 

코드는 다음과 같습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define mod 1000000000
#define check 1023
// 9876543210의 여부 : 1111111111 = 1023 (비트스트링)

int n; // n <= 100
int result;
int dp[101][10][check + 1]; 

// dp[i][j][k] : i번째가 j인데 k만큼 체크된 경우의 수
// 첫 자리 0 안 되므로 첫 번째 1 ~ 9의 dp값 1
// k | (1 << j) : i번째에 j라는 수 들어갔고 기존에 k만큼 체크되었음
// i-1 번째에 j-1, j+1이라는 수 들어올 수 있고, 이 때 k만큼 체크되었음 

// i번째가 0이면 i-1번째는 1밖에 안 됨
// j = 0 : dp[i][j][k | (1 << j)] += dp[i - 1][1][k] % mod
// i번째가 9이면 i-1번째는 8밖에 안 됨
// j = 9 : dp[i][j][k | (1 << j)] += dp[i - 1][8][k] % mod
// 나머지는 +-1 가능
// else : dp[i][j][k | (1 << j)] += (dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k]) % mod
// 최종 합 계산 시 dp[n][...][check] 합하면 됨

// dp 계산 시 10억 미만이고, 10억 + 10억 => int로 가능

void init()
{
  cin >> n;
  memset(dp, 0, sizeof(dp));  

  // 1번째 수 0 X
  for(int i = 1; i <= 9; i++) {
    dp[1][i][1 << i] = 1;
  }

  result = 0;
}

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

void getResult()
{
  for(int i = 0; i <= 9; i++) {
    result += dp[n][i][check];
    result %= mod;
  }

  cout << result;
}

int main() {
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
    
  init();
  getDP();
  getResult();
}