[BOJ][Java] 백준 1562 번: 계단 수

1일 1PS 85일차!

📚 문제

---

[골드 1] - 계단 수

💡 풀이 과정

---

• 처음에는 10 을 기준으로 2차원 dp 를 생성했다.
• 11 자리 계단 수는
  • 8(9~0),(9~0)1, 1(0~9) 3가지가 존재한다.
  • 이때 (9~0), (0~9) 를 10자리 dp 로 생각했다.
  • 하지만 새로운 수를 앞, 뒤에 추가해야하며, 그 과정에서 중복이 발생한다.
• 쉬운 계단 수
  • 위 문제를 먼저 풀어보자.
  • 이 문제는 해당 문제에서 0~9 까지의 수가 모두 들어있는 지 확인만 하면 된다.
    • 이 때 수가 존재하는 지는 비트마스킹을 활용하자.

📌포인트

---

• 시간복잡도
  • 완전 탐색같은 느낌이 있지만 실제로는 O(N * 10 * 1024) 이므로 O(N) 이다.
  • 또한 N < 100 이므로 시간에 부담이 없다.

💻 코드

---

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

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

        int N = Integer.parseInt(st.nextToken());

        // dp[i][j][k] = i자리 수에서 j로 시작하고 k(2진수 비트)를 포함하는 계단 수의 개수
        Long[][][] dp = new Long[N + 1][10][1024];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j < 10; j++) {
                Arrays.fill(dp[i][j], 0L);
            }
        }

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

        for (int i = 2; i <= N; i++) {
            // 0으로 시작하는 경우
            for( int j = 0; j < 1024; j++){
                dp[i][0][j | 1] += dp[i - 1][1][j];
                dp[i][0][j | 1] %= 1000000000;
            }

            // 9로 시작하는 경우
            for( int j = 0; j < 1024; j++){
                dp[i][9][j | 1 << 9] += dp[i - 1][8][j];
                dp[i][9][j | 1 << 9] %= 1000000000;
            }

            // 1 ~ 8로 시작하는 경우
            for (int j = 1; j < 9; j++){
                for( int k = 0; k < 1024; k++){
                    dp[i][j][k | 1 << j] += dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k];
                    dp[i][j][k | 1 << j] %= 1000000000;
                }
            }
        }
        long result = 0;
        for (int i = 0; i < 10; i++){
            result = (result + dp[N][i][1023]) % 1000000000;
        }

        System.out.println(result);
    }
}