BOJ) 계단 수 (1562 번)

계단 수

1562번: 계단 수

45656, 1210123 과 같이 각 자릿 수의 차이가 1씩 나는 수를 계단 수라고 한다.

 

자릿 수를 의미하는 n이 주어질 때, 이러한 계단수가 몇 개 존재하는지 구하는 문제다.

이 때, 모든 계단 수는 0으로 시작하지 않는다.

 

DP와 비트 마스크를 활용해서 푸는 문제로, 각 자릿수, 0 ~9의 수, 비트마스크를 저장할 3차원 정수형 배열 DP를 이용해서 풀었다.

우선, n = 1인 경우, 0 ~ 9는 각각 자신 수 하나를 가진다.

이를 비트마스크로 표현해주면서, n을 증가시켰다.

 

0인 경우에는 0으로 시작할 수 없기 때문에, 0다음에 올 수 있는 수인 1만 dp에 추가시켜주었다.

이외에 1 ~ 8은 각각 앞뒤로 숫자를 추가시켜 계단 수를 만들 수 있기 때문에, 다음 인덱스의 숫자도 함께 체크하면서 dp에 저장했다.

여기서, 9를 따로 체크해주지 않고 배열의 공간을 11로 잡아주어 out of index를 따로 체크하지 않았다.

 

이렇게 저장된 dp의 n 자릿 수에서, 0 ~ 9 까지의 공간을 탐색하며 값을 더해준다.이 때, 모든 숫자 0 ~ 9가 저장된 경우를 찾아야하기 때문에, 모두 저장되어 있는 비트마스크 (1 << 10) -1 번 째 인덱스를 탐색하며 답을 구해준다.

 

또한, 문제의 조건에 1,000,000,000으로 나눈 나머지를 출력하는 조건이 있기 때문에, DP를 저장할 때와 값을 구할 때 모두 MOD를 해주었다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class StairNumber_1562 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    br.close();
    solution(n);
  }

  private static void solution(int n) {
    final int MAX_NUMBER =9, MOD = 1000000000, ALL_VISIT = (1<<10) -1; // 0 ~ 10 비트마스크
    int[][][] dp = new int[n+1][MAX_NUMBER+2][ALL_VISIT+1];
    for(int i=1; i<=MAX_NUMBER; i++) {
      dp[1][i][1 << i] = 1;
    }

    for(int i=2; i<=n; i++) {
      for(int j=0; j<=MAX_NUMBER; j++) {
        for(int k=0; k<=ALL_VISIT; k++) {
          dp[i][j][k | 1 << j] = (dp[i][j][k | 1 << j] + dp[i-1][j+1][k]) % MOD;
          if(j !=0) { // 0인 경우 out of index 방지
            dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % MOD;
          }
        }
      }
    }

    int answer =0;
    for(int i=0; i<=MAX_NUMBER; i++) {
      answer = (answer + dp[n][i][ALL_VISIT]) % MOD;
    }
    System.out.println(answer);
  }
}