[C++] BOJ 1562 - 계단 수

BOJ 1562 - 계단 수 (https://www.acmicpc.net/problem/1562)

 

01. 🔎 문제 탐색

1. 인접한 모든 자리의 차이가 1
2. 수의 길이는 N
3. 0부터 9까지의 숫자가 모두 1번 이상 등장
4. 0으로 시작하면 안 됨

* 위 조건을 모두 만족하고 숫자 길이 N으로 만들 수 있는 계단 수의 개수를 1e9로 모듈러 연산하여 출력

01-1. 가능한 시간 복잡도

• 완전 탐색의 경우, 대략 시간 복잡도가 O(10^N) 으로 실행 시간을 한참 초과
• N의 최댓값이 100으로, 시간 복잡도가 O(N^3) 이하로 구현되어야 함

01-2. 알고리즘 선택

• DP를 통해, 이전 단계에서 사용된 수와 마지막 숫자를 메모이제이션 하는 것으로 각 단계에서 0-9 까지의 수를 한 번 이상 사용하였는 지와 마지막 수가 어떤 수로 끝나는 지에 따라, 다음에 올 수 있는 수를 미리 예측
  (마지막 수가 0일 경우, 다음 수는 1만 올 수 있고, 마지막 수가 9일 경우, 다음 수는 8만 올 수 있음)
• 각 단계에서 각 자리 수가 한 번씩 사용되었는 지 확인하기 위하여 비트 마스킹을 이용

02. 📝 코드 설계하기

1. 숫자 길이 N을 입력
2. 첫 숫자는 0을 제외하고 모든 숫자를 사용할 수 있기 때문에, 1번째 단계의 0을 제외한 모든 숫자에 대하여 메모이제이션
   -> 아직 1단계로 각 마지막 숫자에 대하여 도달할 수 있는 경로가 하나 밖에 없기 때문에, 1을 저장
3. 각 단계(현재 자릿수), 마지막 숫자에 대하여 체크하고 다음 계단 수를 포함한 비트마스크를 계산
4. 다음 단계(다음에 올 마지막 숫자와 마스크)에 현재 단계의 경로 수를 가중
   (0-9까지 숫자 사용 여부와 현재 마지막 숫자를 갖는 가지 수를 가중하는 것으로 상태에 대한 계단 수의 개수를 특정)
5. 3, 4의 과정을 끝까지 반복하여 저장
6. 길이 N에서 마지막 수가 0-9로 끝나며, 마스킹이 모두 1(0-9 모든 수 방문을 뜻함)로 채워진 배열 값을 반환하여 합함

03. 🛠️ 시도별 수정

1회차

• 마지막 결과를 합할 때, 모듈러 연산을 하지 않았음 -> 모듈러 연산 추가

2회차

---

04. 🗝️ 정답 코드

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

const ll MOD = 1e9;
ll dp[101][10][1024];

void func(int N){
  for(int lv = 1; lv < N; lv++){
    for(int back_el = 0; back_el <= 9; back_el++){
      for(int mask = 0; mask < 1024; mask++){
        ll &cur_step = dp[lv][back_el][mask];

        if(0 < back_el) {
          ll new_mask = mask | (1 << (back_el-1));
          ll &next_step = dp[lv+1][back_el-1][new_mask];

          next_step = (cur_step + next_step) % MOD;
        }
        if(back_el < 9) {
          ll new_mask = mask | (1 << (back_el+1));
          ll &next_step = dp[lv+1][back_el+1][new_mask];

          next_step = (cur_step + next_step) % MOD;
        }
      }
    }
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  for(int i = 1; i <= 9; i++) dp[1][i][(1 << i)] = 1;
  ll full_mask = (1 << 10) - 1;

  int N;
  ll result = 0;

  cin >> N;
  func(N);

  for(int i = 0; i <= 9; i++) {
    result = (result + dp[N][i][full_mask]) % MOD;
  };
  cout << result << "\n";
  
  return 0;
}