백준 1562번 - 계단 수

문제

백준 1562번 - 계단 수

아이디어

• 일반적인 계단 수 문제같은 경우 직전의 수만 알면 됐기 때문에 2차원 배열이면 충분했다.
• 하지만 이 문제의 경우 추가적으로 지금까지 사용했던 수들을 기억해야 하기 때문에 비트 마스킹을 활용한 3차원 배열을 사용한다.
• dp[n][i][bit] 를 길이가 n일 때 i(0~9)로 끝난 경우이며 사용한 숫자는 bit로 관리한다.
• 만약 n-1 길이에서 1~8 숫자로 끝났다면 n 길이에서는 이전 숫자 - 1, 이전 숫자 + 1 이 올 수 있다. 0이나 9로 끝났으면 각각 이전 숫자 + 1, 이전 숫자 -1의 숫자만 올 수 있으므로 0과 9는 둘 다 계산되지 않도록 해야 한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

public class BJ_1562 {

    static final int MOD = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        if (n < 10) {
            System.out.println(0);
            return;
        }

        int[][][] dp = new int[n + 1][10][1 << 10];

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

        for (int len = 2; len <= n; len++) {
            for (int num = 0; num <= 9; num++) {
                for (int bit = 0; bit < (1 << 10); bit++) {

                    int now = bit | (1 << num);

                    if (num > 0) dp[len][num][now] += dp[len - 1][num - 1][bit];

                    if (num < 9) dp[len][num][now] += dp[len - 1][num + 1][bit];

                    dp[len][num][now] %= MOD;
                }
            }
        }

        int result = 0;
        for (int i = 0; i < 10; i++) {
            result += dp[n][i][(1 << 10) - 1];
            result %= MOD;
        }
        System.out.println(result);
    }
}