[BOJ] 1562 - 계단 수

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

BOJ - 계단 수

문제 유형: 다이나믹 프로그래밍, 비트마스킹

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 128MB

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

풀이

0~9이므로, 등장여부 상태를 비트마스킹을 이용할 수 있다. (처음에 상태추적을 무식하게 했는데.. 터진다)

0을 LSB부터, 9를 MSB라고 해서 10비트로 상태를 추적할 수 있다. 0은 모든숫자가 없다는 것이고, 1023은 모든 숫자가 있다는 뜻이다.

dp[길이][상태][마지막에 쓰인 숫자] 로 한다.

 

우선, 처음에 길이가 1인 상태는 1~9로 시작하는 것만 유효하다.

그래서, dp[1][1 << i][i](i = 1 ... 9) 를 1로 시작한다.

 

 

이제, 길이 2부터 반복을 시작한다.

모든 상태(0~1024)에 대해서 반복하고,

이전번호(0 ~ 9)에 대해서 반복한다.

이전번호가 0보다 크다면, dp[현재길이][새로운 상태(이전 번호-1과 OR로 마스킹)][이전번호-1]에 dp[이전길이][이전상태][이전번호]를 누적하고 1e9로 나눈다.

만약 이전번호가 9보다 작다면, dp[현재길이][새로운 상태(이전 번호+1과 OR로 마스킹)][이전번호+1]에  dp[이전길이][이전상태][이전번호]를 누적하고 1e9로 나눈다.

최종적으로, 길이가 n이고 모든 숫자를 포함하는, 즉 모든 비트가 켜지고, 마지막 숫자 0~9의 모두의 경우를 더하고 1e9를 나눈 값을 출력한다.

 

코드

C++

#include <bits/stdc++.h>
#define MOD 1000000000
#define ll long long
using namespace std;

int n;
ll dp[101][1024][10]; // dp[length][state][last]

int main() {
  cin >> n;
  for (int i = 1; i <= 9; i++) {
    dp[1][1 << i][i] = 1;
  }

  // DP 점화식
  for (int length = 2; length <= n; length++) {
    for (int state = 0; state < (1 << 10); state++) {
      for (int last = 0; last <= 9; last++) {
        if (dp[length - 1][state][last] == 0) // 이전 길이에서 불가능하다? 그럼 진행 ㄴㄴ
          continue;

        if (last > 0) {
          int nextState = state | (1 << (last - 1));
          dp[length][nextState][last - 1] += dp[length - 1][state][last];
          dp[length][nextState][last - 1] %= MOD;
        }
        if (last < 9) {
          int nextState = state | (1 << (last + 1));
          dp[length][nextState][last + 1] += dp[length - 1][state][last];
          dp[length][nextState][last + 1] %= MOD;
        }
      }
    }
  }

  ll result = 0;
  for (int last = 0; last <= 9; last++) {
    result += dp[n][(1 << 10) - 1][last];
    result %= MOD;
  }

  cout << result << "\n";

  return 0;
}