BOJ 1562 계단 수(Java)

문제 탐색하기

• 인접한 모든 자리의 차이가 1인 수를 계단 수라 한다.
  • 0으로 시작하는 수는 계단수가 아니다.
• 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하여라.
• 정답을 1,000,000,000으로 나눈 나머지를 출력하라.

코드 설계하기

• 0-9 방문 여부를 판정해야 하는데 visited boolean말고 0-9 판정할려면 비트마스킹.
  • 0이면 미방문, 1이면 방문한거로 산정

구현 방법

• 비트마스킹으로 0-9를 사용(방문)했는지 판정한다.
• 첫번째 자리로 1이 못오니까 첫번째 자리 연산에는 1-9를 넣어준다. (초기 상태 설정)
• 두번째 자리부터는 0-9 썼을때 현재 수에서 다음 수가 +1되는 경우 / -1 되는 경우를 판정해서 계산한다.
• 마지막 자리 숫자로 가능한 경우 전부 합산시켜서 답 구한다. dp[N][i][(1 << 10) - 1]

점화식

• 자릿수 전이: 두 번째 자리부터 N번째 자리까지 각 자리수를 채우면서 상태 전이를 수행한다.
• 방문 상태 업데이트: 현재 자리에 j를 배치할 때, nextV = v | (1 << j)를 통해 기존 방문 상태 v에 j를 포함시킨다.
• 계단 수 조건에 따른 전이: 계단 수의 조건에 의해 현재 자리 숫자에 대해 이전 자리 숫자는
  • 만약 j가 0이면, 이전 숫자는 반드시 1 (j+1)
  • 만약 j가 9이면, 이전 숫자는 반드시 8 (j-1)
  • 그 외의 경우, 이전 자리 숫자는 j+1 또는 j-1이 올 수 있다.

// j가 0인 경우
dp[i][0][nextV] += dp[i-1][1][v];

// j가 9인 경우
dp[i][9][nextV] += dp[i-1][8][v];

// 그 외 (j = 1~8)
dp[i][j][nextV] += dp[i-1][j-1][v] + dp[i-1][j+1][v];

시간 복잡도

• 상태로 가능한 값은 O(N×10×1024)이고, N이 최대 100이므로 시간 내에 충분히 연산이 가능하다.

정답 코드 (Java)

import java.io.*;

public class Main {
    private static final int MOD = 1_000_000_000;
    private static long[][][] dp;
    private static int N, sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        dp = new long[N + 1][10][1 << 10];

        // 첫번째 자리에 i가 들어갈 수 잇는 경우
        for (int i = 1; i <= 9; i++) {
            dp[1][i][1 << i] = 1;
        }

        for (int i = 2; i <= N; i++) { // i 번째 자리수
            for (int j = 0; j <= 9; j++){ // 올 수 있는 숫자 순회
                for (int v = 0 ; v < (1<<10); v++){ // 방문 여부

                    int nextV = v | 1 << j;

                    switch (j){
                        case 0:
                            // 0일때는 선행하는 자리수에서 + 1 되는 경우만 존재한다.
                            dp[i][j][nextV] += dp[i - 1][j + 1][v] % MOD;
                            break;
                        case 9:
                            // 0일때는 선행하는 자리수에서 - 1 되는 경우만 존재한다.
                            dp[i][j][nextV] += dp[i - 1][j - 1][v] % MOD;
                            break;
                        default:
                            dp[i][j][nextV] += dp[i - 1][j + 1][v] % MOD + dp[i - 1][j - 1][v] % MOD;
                    }

                    dp[i][j][nextV] %= MOD;
                }
            }
        }

        sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += dp[N][i][(1 << 10) - 1] % MOD;
            sum %= MOD;
        }
        bw.write(sum + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}